/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
長さ N の整数列 A = (A_1, A_2, \dots, A_N) があります。
あなたは次の操作を 0 回以上好きな回数行うことが出来ます。
- 1 \leq i \lt j \leq N を満たす整数対 (i, j) を選び、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
1 番目のテストケースでは、次のように操作を行うことで A を広義単調増加な数列にすることが出来ます。
- (i, j) として (1, 2) を選ぶ。操作後の A は (2, 6, 5) になる。
- (i, j) として (1, 2) を選ぶ。操作後の A は (3, 5, 5) になる。
2 番目のテストケースでは、どのように操作しても A を広義単調増加な数列にすることは出来ません。
Score : 600 points
Problem Statement
You are given an integer sequence A = (A_1, A_2, \dots, A_N) of length N.
You can perform the following operation any number of times, possibly zero:
- Choose an integer pair (i, j) satisfying 1 \leq i \lt j \leq N, and replace A_i with A_i + 1 and A_j with A_j - 1.
Determine whether it is possible to make A a non-decreasing sequence through the operations.
You are given T test cases. Solve each of them.
Constraints
- 1 \leq T \leq 2 \times 10^5
- 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format. Here, \mathrm{case}_i denotes the i-th test case.
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N A_1 A_2 \dots A_N
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
For each test case, if it is possible to make A a non-decreasing sequence through the operations, print Yes; otherwise, print No.
Sample Input 1
3 3 1 7 5 2 9 0 10 607 495 419 894 610 636 465 331 925 724
Sample Output 1
Yes No Yes
In the first test case, you can make A into a non-decreasing sequence by performing the following operations:
- Choose (i, j) = (1, 2). After the operation, A is (2, 6, 5).
- Choose (i, j) = (1, 2). After the operation, A is (3, 5, 5).
In the second test case, you cannot make A into a non-decreasing sequence no matter how you perform the operations.