A. Сортировка двойками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. За одну операцию вы делаете следующее:

  • Выбираете неотрицательное целое число $$$m$$$, такое что $$$2^m \leq n$$$.
  • Вычитаете $$$1$$$ из $$$a_i$$$ для всех целых $$$i$$$, таких что $$$1 \leq i \leq 2^m$$$.

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

Массив называется неубывающим, если $$$a_i \leq a_{i + 1}$$$ для всех целых $$$i$$$, таких что $$$1 \leq i \leq n - 1$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 20$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — элементы массива $$$a$$$ ($$$0 \leq a_i \leq 1000$$$).

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

Для каждого набора входных данных выведите «YES» если можно отсортировать массив, и «NO» иначе.

Пример
Входные данные
8
5
1 2 3 4 5
5
6 5 3 4 4
9
6 5 5 7 5 6 6 8 7
4
4 3 2 1
6
2 2 4 5 3 2
8
1 3 17 19 27 57 179 13
5
3 17 57 179 92
10
1 2 3 4 0 6 7 8 9 10
Выходные данные
YES
YES
YES
NO
NO
NO
YES
YES
Примечание

В первом наборе входных данных массив уже отсортирован по неубыванию, к нему можно не применять никаких действий.

Во втором наборе входных данных можно выбрать $$$m = 1$$$ два раза и получить массив $$$[4, 3, 3, 4, 4]$$$. Затем можно выбрать $$$m = 0$$$ один раз и получить отсортированный по неубыванию массив $$$[3, 3, 3, 4, 4]$$$.

В третьем наборе входных данных можно выбрать $$$m = 0$$$ один раз и получить массив $$$[5, 5, 5, 7, 5, 6, 6, 8, 7]$$$. Далее можно выбрать $$$m = 2$$$ два раза и получить массив $$$[3, 3, 3, 5, 5, 6, 6, 8, 7]$$$. Затем выбрать $$$m = 3$$$ один раз и получить отсортированный по неубыванию массив $$$[2, 2, 2, 4, 4, 5, 5, 7, 7]$$$.

В четвертом и пятом наборе входных данных можно доказать, что нельзя отсортировать массив этими операциями.