Equalized forests have all the trees of same heights.
You're given current height of trees in a forest. This forest is in a linear fashion, i.e. all the trees are in one straight line. You have two types of watering vessels:
Vessel 1: this Vessel waters only one tree, and increases its height by two (+2).
Vessel 2: this Vessel waters two adjacent trees, but has a smaller volume, so height of both the trees only increase by one (+1). Also, the height of the two trees must be same for the water of this Vessel to take effect. So, if the height of both adjacent trees are same, both of their heights increase by 1, otherwise they increase by zero.
Tree[i] and Tree[i+1] are considered as adjacent trees, for each valid i and i+1
You have an unlimited supply of water. Is it possible to equalize the forest after watering them? Print "YES" if it possible, "NO" otherwise.
NOTE: Please use fast i/o for solving this problem.
Input Format: The first line contains number of test cases t (1≤t≤166666). For the next t lines:
The first line contains integer n (1≤n≤100000), the number of trees in the forest. Next line contains n space-separated integers i (0≤i<109), the heights of trees.
It is guaranteed that the sum of n over all test cases doesn’t exceed 106.
Output Format: For each test case print “YES” if it is possible to Equalize the forest, “NO” otherwise.
In the first test case, the intial arrangement is: [ 4, 3, 1 ]. We use Vessel 1 on Tree[3], increasing its height by 2. New forest is [ 4, 3, 3 ]. Now, since Tree[2]==Tree[3]=3, we can use Vessel 2 on them, increasing both of their heights by 1 and equalising the forest: [ 4, 4, 4]
In the third test case, since Tree[2]=tree[3]=1, we can simply apply Vessel 2 on them and equalise the forest as: [ 2, 2, 2, 2]
In the second test case, there is no way to equalize the forest
