Nasser and Equal Array#13082
Nasser has an array of positive integers. He may perform the following operations any number of times (possibly zero), in any order:
1. Choose an index (1 \le i \le n) and increase a_i by .
2. Choose a segment [l, r] (1 \le l < r \le n) such that a_l = a_{l+1} = \ldots = a_r, and increase each of a_l, a_{l+1}, \ldots, a_r by .
Note that the second operation requires the chosen segment to contain at least two elements, all of which are equal at the moment of the operation. For example, if a = [4, 5, 5, 7], the segment can be chosen, but the segments and cannot.
Determine whether Nasser can make all elements of the array equal.
Each test contains multiple test cases. The first line contains a single integer (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer (1 \le n \le 2 \cdot 10^5) — the size of the array.
The second line of each test case contains integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — the elements of the array.
It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.
Print YES if it is possible to make all elements equal using the allowed operations. Otherwise, print NO.
You may output the answer in any letter case. For example, the strings yEs, yes, Yes, and YES will all be accepted as valid positive responses.
Example 1
In the first test case, a = [1, 2]. The difference a_2 - a_1 equals . The first operation changes this difference by exactly , so it always stays odd and never becomes . The second operation can only be applied to two equal adjacent elements, so it can never be applied here. Therefore the elements can never become equal.
In the second test case, a = [2, 4]. Apply the first operation with i = 1: [2, 4] \to [4, 4].
In the fourth test case, a = [3, 2, 2, 1]. Apply the second operation with [l, r] = [2, 3]: [3, 2, 2, 1] \to [3, 3, 3, 1]. Then apply the first operation with i = 4: [3, 3, 3, 1] \to [3, 3, 3, 3].
Subtask ( points) : No additional constraints.