G. Рациональная пузырьковая сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность $$$a_1,a_2,\ldots,a_n$$$, состоящая из рациональных чисел. Изначально каждый $$$a_i$$$ является целым числом от $$$0$$$ до $$$10^6$$$ включительно.

Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • Выберите индекс $$$i$$$ такой, что $$$1 \le i \lt n$$$, и пусть $$$z=\frac{{1}}{{2}}(a_{i}+a_{i+1})$$$.
  • Затем присвойте и $$$a_i$$$, и $$$a_{i+1}$$$ значение $$$z$$$.

Например, пусть $$$a=[0,15,0]$$$. Если выполнить операцию с $$$i=2$$$, то $$$a$$$ станет равным $$$[0,\color{red}{7.5},\color{red}{7.5}]$$$.

Определите, можно ли сделать массив $$$a$$$ отсортированным по неубыванию.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).

Вторая строка каждого набора входных данных содержит $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 10^6$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите «Yes», если можно сделать массив $$$a$$$ отсортированным в неубывающем порядке, и «No» в противном случае.

Вы можете выводить ответ в любом регистре. Например, строки «yEs», «yes» и «YES» также будут распознаны как положительные ответы.

Пример
Входные данные
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
Выходные данные
No
Yes
No
Yes
No
Yes
Примечание

Для первого набора входных данных невозможно сделать массив $$$a$$$ отсортированным в неубывающем порядке.

Второй набор входных данных разобран в условии.

Для четвертого набора входных данных массив $$$a$$$ можно отсортировать в неубывающем порядке следующим образом: $$$[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}}}]$$$.