DMOPC '22 Contest 1 P1 - Up-down Sequence

View as PDF

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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.

Constraints

The sum of over all test cases does not exceed .

Input Specification

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.

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 .

For the third test case, one may convert the sequence to .