Сталинская сортировка — это юмористический алгоритм сортировки. Вместо траты сил на сортировку элементов должным образом, элементы на неправильных позициях просто удаляются. Сложность алгоритма — \(\mathcal{O}(n)\).
Алгоритм устроен следующим образом: начиная со второго элемента массива, если текущий элемент строго меньше предыдущего элемента (игнорируя те, которые уже были удалены), то удалите текущий элемент. Продолжайте проход по массиву до тех пор, пока он не будет отсортирован по неубыванию. Например, массив \([1, 4, 2, 3, 6, 5, 5, 7, 7]\) превращается в \([1, 4, 6, 7, 7]\) после сталинской сортировки.
Назовём массив уязвимым, если вы можете отсортировать его в невозрастающем порядке, применив сталинскую сортировку к любым его подотрезкам\(^{\text{∗}}\) столько угодно раз.
Для массива \(a\), состоящего из \(n\) целых чисел, определите минимальное количество элементов, которое нужно удалить из массива, чтобы он стал уязвимым.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество элементов, которое нужно удалить из массива, чтобы он стал уязвимым.
Примечание
В первом наборе входных данных оптимально будет удалить числа \(3\) и \(9\). Тогда у нас останется \(a = [6, 4, 2, 5, 2]\). Чтобы показать, что этот массив уязвим, мы можем сначала применить сталинскую сортировку к подмассиву \([4, 2, 5]\), чтобы получить \(a = [6, 4, 5, 2]\), а затем применить сталинскую сортировку к подмассиву \([6, 4, 5]\), чтобы получить массив \(a = [6, 2]\), который является невозрастающим.
Во втором наборе входных данных массив уже является невозрастающим, поэтому нам не нужно удалять элементы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
7
3 6 4 9 2 5 2
5
5 4 4 2 2
8
2 2 4 4 6 6 10 10
1
1000
9
6 8 9 10 12 9 7 5 4
7
300000000 600000000 400000000 900000000 200000000 400000000 200000000
|
2
0
6
0
4
2
|