Codeforces Round 786 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

implementation

sortings

*1200

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. A-B-C Sort

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$: 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$$$: 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.

Can you make array $$$c$$$ sorted in non-decreasing order?

Input

The first line contains a single integer $$$t$$$ ($$$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 \le n \le 2 \cdot 10^5$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the array $$$a$$$ itself.

It's guaranteed that the sum of $$$n$$$ doesn't exceed $$$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).

Example

Input

343 1 5 333 2 117331

Output

YES NO YES

Note

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

Step $$$1$$$:

$$$a$$$ | $$$[3, 1, 5, 3]$$$ | $$$\Rightarrow$$$ | $$$[3, 1, 5]$$$ | $$$\Rightarrow$$$ | $$$[3, 1]$$$ | $$$\Rightarrow$$$ | $$$[3]$$$ | $$$\Rightarrow$$$ | $$$[]$$$ |

$$$b$$$ | $$$[]$$$ | $$$[\underline{3}]$$$ | $$$[3, \underline{5}]$$$ | $$$[3, \underline{1}, 5]$$$ | $$$[3, \underline{3}, 1, 5]$$$ |

Step $$$2$$$:

$$$b$$$ | $$$[3, 3, \underline{1}, 5]$$$ | $$$\Rightarrow$$$ | $$$[3, \underline{3}, 5]$$$ | $$$\Rightarrow$$$ | $$$[\underline{3}, 5]$$$ | $$$\Rightarrow$$$ | $$$[\underline{5}]$$$ | $$$\Rightarrow$$$ | $$$[]$$$ |

$$$c$$$ | $$$[]$$$ | $$$[1]$$$ | $$$[1, 3]$$$ | $$$[1, 3, 3]$$$ | $$$[1, 3, 3, 5]$$$ |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/19/2024 18:09:47 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|