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

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