An up-down sequence is any sequence where the elements alternate between increasing and decreasing. Formally, a sequence of integers is considered to be an up-down sequence if for each , either or . Given a sequence of 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 test cases.
The sum of over all test cases does not exceed .
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line contains an integer , the number of test cases. The next lines describe the test cases.
The first line of each test case contains a single integer .
The second line of each test case contains integers . Forgotten elements are denoted by s in the sequence.
For each test case, output a single line containing
YES if it is possible to make it an up-down sequence or
4 7 1 0 2 5 3 0 2 5 3 0 1 2 3 4 1 0 0 1 3 6 6 0
YES NO YES NO
Explanation for Sample
For the first test case, one may convert the sequence to .
For the third test case, one may convert the sequence to .