K. Powerful Swaps (Hard Version)
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Keys got caught lacking, sleeping in English class, and was forcefully shaken awake by the teacher. (This would never have happened if Keys had instead slept in the sleeping bag.) As punishment, he was given this task to solve.

He was given an array of integers $$$a$$$ of length $$$n$$$. His goal is to find if he can sort the array using only valid swaps. Define a swap as valid if for the $$$j$$$-th swap, elements $$$a_i$$$ and $$$a_{i + 1}$$$ are swapped, and $$$min(a_i, a_{i + 1}) \ge j$$$.

Unfortunately, Keys enjoys sleeping in his sleeping bag too much to solve the problem. Please help solve the problem for him before he gets in trouble!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print YES if it is possible to sort the array; otherwise, print NO. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
3
4
2 1 4 3
3
2 1 1
5
7 5 2 4 7
Output
YES
NO
YES
Note

For the first test case, a valid sequence of swaps is the following: For the $$$1$$$-st swap, swap $$$a_1$$$ and $$$a_2$$$. This is valid since $$$min(a_1, a_2) = 1$$$, and $$$1 \ge 1$$$. For the $$$2$$$-nd swap, swap $$$a_3$$$ and $$$a_4$$$. This is valid since $$$min(a_3, a_4) = 3$$$, and $$$3 \ge 2$$$. After these two swaps, the array is sorted.

For the second test case, it can be seen that it is impossible to sort the array since the $$$2$$$ is not able to make it to the third position.