A-B-C Sort Codeforces Solution | Codeforces Problem Solution 2022

A-B-C Sort Codeforces Solution | Codeforces Problem Solution 2022

D. A-B-C Sort

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given three arrays 𝑎$a$, 𝑏$b$ and 𝑐$c$. Initially, array 𝑎$a$ consists of 𝑛$n$ elements, arrays 𝑏$b$ and 𝑐$c$ are empty.

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

• Step 1$1$: 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 2$2$: 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 Click Below:-  CLICK HERE

Input

The first line contains a single integer 𝑡$t$ (1≤𝑡≤2⋅104$1\le t\le 2\cdot {10}^4$) — the number of test cases. Next 𝑡$t$ cases follow.

The first line of each test case contains the single integer 𝑛$n$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$) — the length of array 𝑎$a$.

Number Transformation Codeforces Solution

Remove Directed Edges Codeforces Solution

Desktop Rearrangement Codeforces Solution

Breaking the Wall Codeforces Solution

A-B-C Sort Codeforces Solution

Infinite Replacement Codeforces Solution 

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤106$1\le a_i\le {10}^6$) — the array 𝑎$a$ itself.

It's guaranteed that the sum of 𝑛$n$ doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

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

Join Now for Solution:-