Statement : G. Rational Bubble Sort

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.

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$.

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.

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}}}]$.