[Solution] A-B-C Sort solution codeforces

A-B-C Sort solution codeforces – You are given three arrays 𝑎a𝑏b and 𝑐c. Initially, array 𝑎a consists of 𝑛n elements, arrays 𝑏b and 𝑐c are empty.

[Solution] A-B-C Sort solution codeforces

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

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

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

[Solution] A-B-C Sort solution codeforces

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

The first line of each test case contains the single integer 𝑛n (1𝑛21051≤n≤2⋅105) — the length of array 𝑎a.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1061≤ai≤106) — the array 𝑎a itself.

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

Output

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

[Solution] A-B-C Sort solution codeforces

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 𝑎=[3,1,5,3]a=[3,1,5,3]:

Step 11:

𝑎a [3,1,5,3][3,1,5,3] [3,1,5][3,1,5] [3,1][3,1] [3][3] [][]
𝑏b [][] [3⎯⎯][3_] [3,5⎯⎯][3,5_] [3,1⎯⎯,5][3,1_,5] [3,3⎯⎯,1,5][3,3_,1,5]

A-B-C Sort solution codeforces

Step 22:

𝑏b [3,3,1⎯⎯,5][3,3,1_,5] [3,3⎯⎯,5][3,3_,5] [3⎯⎯,5][3_,5] [5⎯⎯][5_] [][]
𝑐c [][] [1][1] [1,3][1,3] [1,3,3][1,3,3] [1,3,3,5][1,3,3,5]

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

 

For Solution

Click here

Leave a Comment