DMOPC '22 Contest 1 P1 - Up-down Sequence

View as PDF

Submit solution

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

Problem type

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.


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 0s 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

1 0 2 5 3 0 2
3 0 1 2 3
1 0 0 1
6 6 0

Sample Output


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


There are no comments at the moment.