Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4072
Origami

Time Limit: 1 Second      Memory Limit: 131072 KB

Chiaki has a very big sheet of paper. This sheet has a form of rectangle with dimensions $1 \times n$ and numbers from $1$ to $n$ was written on each small $1 \times 1$ grid. Chiaki would like to fold the paper using the following operations:

1. Fold the sheet of paper at position $p_i$ to the right. After this query the leftmost part of the paper with dimensions $1 \times p_i$ must be above the rightmost part of the paper with dimensions $1 \times ([\textit{current width of sheet}] - p_i$).
2. Fold the sheet of paper at position $p_i$ to the left. After this query the rightmost part of the paper with dimensions $1 \times ([\textit{current width of sheet}] - p_i$) must be above the leftmost part of the paper with dimensions $1 \times p_i$.

After performing the above operations several times, the sheet of paper has dimensions $1 \times 1$. If we write down the number on each grid from top to bottom, we will have a permutation of $n$.

Now given a permutation of $n$, Chiaki would like to know whether it is possible to obtain the permutation using the above operations.

#### Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^6$), indicating the length of the paper.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, which is a permutation of $n$, indicating the integers marked in the grids of the resulting sheet of paper from top to bottom.

It's guaranteed that the sum of $n$ in all test cases will not exceed $10^6$.

#### Output

For each test case output one line. If it's possible to obtain the permutation, output "Yes" (without the quotes), otherwise output "No" (without the quotes).

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

#### Sample Output

Yes
Yes
No

Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status