An up-down sequence is any sequence where the elements alternate between increasing and decreasing. Formally, a sequence $A$ of $N$ integers is considered to be an up-down sequence if for each $1<i<N$, either $A_{i-1}<A_i>A_{i+1}$ or $A_{i-1}>A_i<A_{i+1}$. Given a sequence of $N$ integers, some of which are forgotten, you must determine whether it is possible to replace each forgotten element with any integer so that the resulting sequence is an up-down sequence. To ensure the integrity of your solution, there will be $T$ test cases.

Constraints

$1\le T\le {10}^6$

$3\le N\le {10}^6$

$0\le A_i\le {10}^9$

The sum of $N$ over all test cases does not exceed ${10}^6$.

Subtask 1 [20%]

$1\le A_i\le {10}^9$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains an integer $T$, the number of test cases. The next $2T$ lines describe the test cases.

The first line of each test case contains a single integer $N$.

The second line of each test case contains $N$ integers $A_1,A_2,\dots ,A_N$. Forgotten elements are denoted by $0$s in the sequence.

Output Specification

For each test case, output a single line containing YES if it is possible to make it an up-down sequence or NO otherwise.

Sample Input

4
7
1 0 2 5 3 0 2
5
3 0 1 2 3
4
1 0 0 1
3
6 6 0

Sample Output

YES
NO
YES
NO

Explanation for Sample

For the first test case, one may convert the sequence to $[1,3,2,5,3,4,2]$.

For the third test case, one may convert the sequence to $[1,-1,2,1]$.