← 返回题目列表

AtCoder · arc185_b

B. +1 和 -1

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个整数序列 A = (A_1, A_2, \dots, A_N) 长度 N.
您可以执行以下操作任意次数,可能为零:

  • 选择一个整数对 (i, j) 满意 1 \leq i \lt j \leq N,并替换 A_i 与 A_i + 1 和 A_j 与 A_j - 1.

判断是否可以使 A 通过操作的非递减序列。

你被给予 T 测试用例。解决它们中的每一个。

约束

  • 1 \leq T \leq 2 \times 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 总和 N 所有测试用例最多 2 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出。在这里, \mathrm{case}_i 表示 i- 第一个测试用例。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
对于每个测试用例,是否可以使 A 一个非减序列通过运算,打印 Yes;否则,打印 No.


示例输入 1

3
3
1 7 5
2
9 0
10
607 495 419 894 610 636 465 331 925 724

示例输出 1

Yes
No
Yes

在第一个测试用例中,您可以使 通过执行以下操作将 A 转换为非递减序列:

  • 选择 (i, j) = (1, 2)。手术后, A is (2, 6, 5).
  • 选择 (i, j) = (1, 2)。手术后, A is (3, 5, 5).

在第二个测试用例中,您不能使 无论您如何执行操作, A 都会变成非递减序列。