G. Rational Bubble Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$a_1,a_2,\ldots,a_n$$$ consisting of rational values. Initially, each $$$a_i$$$ is an integer from $$$0$$$ to $$$10^6$$$ inclusive.

You can perform the following operation any number of times (possibly zero):

  • Select an index $$$i$$$ such that $$$1 \le i \lt n$$$, and let $$$z=\frac{{1}}{{2}}(a_{i}+a_{i+1})$$$.
  • Then, set $$$a_i$$$ and $$$a_{i+1}$$$ both to the value of $$$z$$$.

For example, let $$$a=[0,15,0]$$$. If you perform the operation on $$$i=2$$$, $$$a$$$ becomes $$$[0,\color{red}{7.5},\color{red}{7.5}]$$$.

Please determine if it is possible to make $$$a$$$ sorted in non-decreasing order.

Input

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

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

The second line of each test case contains $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 10^6$$$).

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

Output

For each test case, output "Yes" if it is possible to make $$$a$$$ sorted in non-decreasing order, or "No" otherwise.

You can output the answer in any case. For example, the strings "yEs", "yes", and "YES" will also be recognized as positive responses.

Example
Input
6
3
24 0 0
3
0 15 0
4
15 14 5 6
4
0 1 0 0
8
8 7 6 5 4 3 2 1
6
4 1 5 4 1 1
Output
No
Yes
No
Yes
No
Yes
Note

For the first test case, it is impossible to make $$$a$$$ sorted in non-decreasing order.

The second test case is explained in the statement.

For the fourth test case, $$$a$$$ can be sorted in non-decreasing order as $$$[0,1,0,0] \to [0,\color{red}{\frac{{1}}{{2}}},\color{red}{\frac{{1}}{{2}}},0] \to [\color{red}{\frac{{1}}{{4}}},\color{red}{\frac{{1}}{{4}}},\frac{{1}}{{2}},0] \to [\frac{{1}}{{4}},\frac{{1}}{{4}},\color{red}{\frac{{1}}{{4}}},\color{red}{\frac{{1}}{{4}}}]$$$.