D. Permutation Swaps
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Consider the following recursive procedure, written in pseudocode, which transforms an input array into a permutation of its elements: 


function generate(sequence b):
    if size of b is 1:
        return b
    else:
        split b into two non-empty contiguous subarrays, b_1 and b_2
        optionally, swap b_1 and b_2
        b_1 = generate(b_1)
        b_2 = generate(b_2)
        concatenate b_1 and b_2 into b', in this order
        return b'
    end if

In other words, at each step, the array is split into two contiguous subarrays (not necessarily of equal length). You may optionally swap the order of the two subarrays before recursing on each. After both subarrays are recursively processed using the same procedure, they are concatenated in their current order to form the result.

Note that the final output of the procedure may vary depending on how the array is split at each step and whether or not a swap is applied.

You are given an array $$$a$$$ of $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$, which is a permutation of integers from $$$1$$$ to $$$n$$$. Your task is to determine if it is possible for array $$$a$$$ to be the output of generate function when applied to the identity permutation $$$[1,2,\ldots, n]$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ non-negative integers $$$a_1,a_2,\ldots,a_n$$$ — the elements of the array $$$a$$$.

  • $$$1 \le t \le 10^4$$$
  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le a_i \le n$$$
  • It is guaranteed that $$$a_1, a_2, \ldots, a_n$$$ is a permutation of $$$1,2,\ldots, n$$$.
  • It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output

For each test case, output 'Yes' if it is possible for array $$$a$$$ to be the output of the generate function when applied to the identity permutation $$$[1,2,\ldots, n]$$$. Otherwise, output 'No'.

Example
Input
5
5
2 1 5 3 4
4
3 1 4 2
1
1
10
4 2 9 1 10 5 8 3 7 6
8
4 5 2 1 3 8 6 7
Output
Yes
No
Yes
No
Yes