Question
Equalize Array
Mira was given an array of length N as part of a coding challenge. She can choose any index i (where 1 < i < N) and decrease the element at that index if it’s not smaller than both of its neighbors (i.e., Ai ≥ Ai−1 and Ai ≥ Ai+1). Her task is to determine if it’s possible to make all elements in the array equal by performing this operation multiple times. Can you figure out if it’s possible?
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.