A-B-C Sort solution codeforces

A-B-C Sort solution codeforces

 

You are given three arrays aabb and cc. Initially, array aa consists of nn elements, arrays bb and cc are empty.

You are performing the following algorithm that consists of two steps:

  • Step 11: while aa is not empty, you take the last element from aa and move it in the middle of array bb. If bb currently has odd length, you can choose: place the element from aa to the left or to the right of the middle element of bb. As a result, aa becomes empty and bb consists of nn elements.
  • Step 22: while bb is not empty, you take the middle element from bb and move it to the end of array cc. If bb currently has even length, you can choose which of two middle elements to take. As a result, bb becomes empty and cc now consists of nn elements.

Refer to the Note section for examples.Can you make array cc sorted in non-decreasing order?

Input

The first line contains a single integer tt (1t21041≤t≤2⋅104) — the number of test cases. Next tt cases follow.

The first line of each test case contains the single integer nn (1n21051≤n≤2⋅105) — the length of array aa.

The second line of each test case contains nn integers a1,a2,,ana1,a2,…,an (1ai1061≤ai≤106) — the array aa itself.

It’s guaranteed that the sum of nn doesn’t exceed 21052⋅105.

Output

For each test, print YES (case-insensitive), if you can make array cc sorted in non-decreasing order. Otherwise, print NO (case-insensitive).

Example

input

Copy
3
4
3 1 5 3
3
3 2 1
1
7331

output

Copy
YES
NO
YES
Note

In the first test case, we can do the following for a=[3,1,5,3]a=[3,1,5,3]:

Step 11:

aa [3,1,5,3][3,1,5,3] [3,1,5][3,1,5] [3,1][3,1] [3][3] [][]
bb [][] [3][3_] [3,5][3,5_] [3,1,5][3,1_,5] [3,3,1,5][3,3_,1,5]

 

Step 22:

bb [3,3,1,5][3,3,1_,5] [3,3,5][3,3_,5] [3,5][3_,5] [5][5_] [][]
cc [][] [1][1] [1,3][1,3] [1,3,3][1,3,3] [1,3,3,5][1,3,3,5]

As a result, array c=[1,3,3,5]c=[1,3,3,5] and it’s sorted.

Leave a Comment