Question
Naina's Task
Naina is given an array A of length N. She can perform the following operation on it:
Choose any index i such that 1 < i < N and Ai is not smaller than either of its neighbors, i.e, both Ai ≥ Ai−1 and Ai ≥ Ai+1 are true. Then, decrease Ai by 1.
Is it possible to make all the elements of A equal by performing this operation several (possibly, zero) times?
Choose any index i such that 1 < i < N and Ai is not smaller than either of its neighbors, i.e, both Ai ≥ Ai−1 and Ai ≥ Ai+1 are true. Then, decrease Ai by 1.
Is it possible to make all the elements of A equal by performing this operation several (possibly, zero) times?
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains N - the number of elements in A.
The second line of each test case contains N space-separated integers, denoting the array A.
Constraints
1 ≤ T ≤ 105
1 ≤ N ≤ 2x105
1 ≤ Ai ≤ 109
Note: The sum of N over all test cases won't exceed 2x105.
Each test case consists of two lines of input.
The first line of each test case contains N - the number of elements in A.
The second line of each test case contains N space-separated integers, denoting the array A.
Constraints
1 ≤ T ≤ 105
1 ≤ N ≤ 2x105
1 ≤ Ai ≤ 109
Note: The sum of N over all test cases won't exceed 2x105.
Output
For each test case, output on a new line the answer: "Yes" if it is possible to make all the elements of A equal, and "No" otherwise (without quotes).
Example
Sample Input
3
1
1
4
1 3 2 1
7
2 4 5 1 4 5 3
Sample Output
Yes
Yes
No
Explanation
Test case 1: A contains only a single element, so all its elements are already equal.
Test case 2: Perform operations as follows:
Choose i = 2, and decrease it, to get [1, 2, 2, 1].
Choose i = 2 again and decrease it, to get [1, 1, 2, 1].
Choose i = 3 and decrease it, to get [1, 1, 1, 1].
All elements are equal now.
3
1
1
4
1 3 2 1
7
2 4 5 1 4 5 3
Sample Output
Yes
Yes
No
Explanation
Test case 1: A contains only a single element, so all its elements are already equal.
Test case 2: Perform operations as follows:
Choose i = 2, and decrease it, to get [1, 2, 2, 1].
Choose i = 2 again and decrease it, to get [1, 1, 2, 1].
Choose i = 3 and decrease it, to get [1, 1, 1, 1].
All elements are equal now.