Андреа придумал, как он считает, новый алгоритм сортировки для массивов длины \(n\). Алгоритм работает следующим образом.
Изначально имеется массив из \(n\) целых чисел \(a_1,\, a_2,\, \dots,\, a_n\). Затем выполняется \(k\) шагов.
Для каждого \(1\le i\le k\) на \(i\)-м шаге сортируется подпоследовательность массива \(a\) с индексами \(j_{i,1}< j_{i,2}< \dots< j_{i, q_i}\), не меняя значений с остальными индексами. Таким образом, в результате подпоследовательность \(a_{j_{i,1}},\, a_{j_{i,2}},\, \dots,\, a_{j_{i,q_i}}\) отсортирована, а все остальные элементы \(a\) остались нетронутыми.
Андреа, желая поделиться своим открытием с научным сообществом, отправил небольшую статью с описанием своего алгоритма в журнал «Анналы алгоритмов сортировки», а вы являетесь рецензентом статьи (то есть человеком, который должен оценить правильность статьи). Вы должны решить, является ли алгоритм Андреа правильным, то есть сортирует ли он любой массив \(a\) из \(n\) целых чисел.
Примечание
Объяснение первого примера: Алгоритм состоит из \(3\) шагов. Первый сортирует подпоследовательность \([a_1, a_2, a_3]\), второй сортирует подпоследовательность \([a_2, a_3, a_4]\), третий сортирует подпоследовательность \([a_1,a_2]\). Например, если первоначально \(a=[6, 5, 6, 3]\), то алгоритм преобразует массив следующим образом (сортируемая подпоследовательность выделена красным цветом) \(\) [{\color{red}6},{\color{red}5},{\color{red}6},3] \rightarrow [5, {\color{red}6}, {\color{red}6}, {\color{red}3}] \rightarrow [{\color{red}5}, {\color{red}3}, 6, 6] \rightarrow [3, 5, 6, 6] \,.\(\) Можно доказать, что для любого начального массива \(a\), в конце алгоритма массив \(a\) будет отсортирован.
Объяснение второго примера: Алгоритм состоит из \(3\) шагов. На первом сортируется подпоследовательность \([a_1, a_2, a_3]\), на втором — подпоследовательность \([a_2, a_3, a_4]\), на третьем — подпоследовательность \([a_1,a_3,a_4]\). Например, если первоначально \(a=[6, 5, 6, 3]\), то алгоритм преобразует массив следующим образом (сортируемая подпоследовательность выделена красным цветом) \(\) [{\color{red}6},{\color{red}5},{\color{red}6},3] \rightarrow [5, {\color{red}6}, {\color{red}6}, {\color{red}3}] \rightarrow [{\color{red}5}, 3, {\color{red}6}, {\color{red}6}] \rightarrow [5, 3, 6, 6] \,.\(\) Обратите внимание, что \(a=[6,5,6,3]\) является примером массива, который не сортируется алгоритмом.
Объяснение третьего примера: Алгоритм состоит из \(4\) шагов. Первые \(3\) шага ничего не делают, так как сортируют подпоследовательности длиной \(1\), тогда как четвертый шаг сортирует подпоследовательность \([a_1,a_3]\). Например, если первоначально \(a=[5,6,4]\), алгоритм преобразует массив следующим образом (подпоследовательность, которая сортируется, выделена красным цветом) \(\) [{\color{red}5},6,4] \rightarrow [5,{\color{red}6},4] \rightarrow [5,{\color{red}6},4] \rightarrow [{\color{red}5},6,{\color{red}4}]\rightarrow [4,6,5] \,.\(\) Обратите внимание, что \(a=[5,6,4]\) - это пример массива, который не сортируется алгоритмом.
Пояснение четвертого примера: Алгоритм состоит из \(2\) шагов. На первом этапе сортируются подпоследовательности \([a_2,a_3,a_4]\), на втором - весь массив \([a_1,a_2,a_3,a_4,a_5]\). Например, если изначально \(a=[9,8,1,1,1]\), алгоритм преобразует массив следующим образом (подпоследовательность, которая получает сортировку, выделена красным цветом) \(\) [9,{\color{red}8},{\color{red}1},{\color{red}1},1] \rightarrow [{\color{red}9},{\color{red}1},{\color{red}1},{\color{red}8},{\color{red}1}] \rightarrow [1,1,1,8,9] \,.\(\) Поскольку на последнем шаге сортируется весь массив, очевидно, что для любого начального массива \(a\) в конце алгоритма массив \(a\) будет отсортирован.