A-B-C Sort solution codeforces
You are given three arrays, and . Initially, array consists of elements, arrays and are empty.
You are performing the following algorithm that consists of two steps:
- Step the last element from and move it in the middle of array . If currently has odd length, you can choose: place the element from to the left or to the right of the middle element of . As a result, becomes empty and consists of elements. : while is not empty, you take
- Step the middle element from and move it to the end of array . If currently has even length, you can choose which of two middle elements to take. As a result, becomes empty and now consists of elements. : while is not empty, you take
Refer to the Note section for examples.Can you make arraysorted in non-decreasing order?
The first line contains a single integer( ) — the number of test cases. Next cases follow.
The first line of each test case contains the single integer( ) — the length of array .
The second line of each test case containsintegers ( ) — the array itself.
It’s guaranteed that the sum ofdoesn’t exceed .
For each test, print YES (case-insensitive), if you can make array sorted in non-decreasing order. Otherwise, print NO (case-insensitive).
3 4 3 1 5 3 3 3 2 1 1 7331
YES NO YES
In the first test case, we can do the following for:
As a result, arrayand it’s sorted.