Дан массив целых чисел \(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\).
Примечание
В первом наборе входных данных массив уже отсортирован по неубыванию, к нему можно не применять никаких действий.
Во втором наборе входных данных можно выбрать \(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]\).
В четвертом и пятом наборе входных данных можно доказать, что нельзя отсортировать массив этими операциями.