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]~.