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.

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

Rational Bubble Sort

Examples