Welcome to ZOJ
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).

Sample Input

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