Сортировка Таноса — суперзлодейский алгоритм сортировки, работающий следующим образом: если массив не отсортирован, щелкните пальцами*, чтобы уничтожить первую или вторую половину элементов, и повторите процесс.
Вам дан входной массив. Какова максимальная длина отсортированного массива, который можно из него получить, используя сортировку Таноса?
*Требует наличия Перчатки бесконечности.
Выходные данные
Выведите максимальную длину отсортированного массива, который можно получить, используя сортировку Таноса. Элементы итогового массива должны быть отсортированы в порядке неубывания.
Примечание
В первом примере массив уже отсортирован, и можно обойтись без щелчков.
Во втором примере входной массив содержит отсортированный подмассив из 4 элементов, но увы, удалять элементы из разных частей массива за один щелчок нельзя. Можно удалять только все элементы из первой или из второй половины массива, поэтому потребуется два щелчка, чтобы получить отсортированный массив длины 2.
В третьем примере массив отсортирован в порядке убывания, и спасти от уничтожения получится только один элемент.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 2 4
|
4
|
|
2
|
8
11 12 1 2 13 14 3 4
|
2
|
|
3
|
4
7 6 5 4
|
1
|