| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 24 | 5 | 5 | 21.739% |
У Уолтера Беккета был замечательный отсортированный массив, однако, после множества экпериментов произошло непредвиденное: а именно, массив перестал быть отсортированным!
Казалось бы, что сложного в том, чтобы отсортировать массив? Но Уолтер и здесь решил провести эксперимент. Он хочет отсортировать массив используя только две операции:
Таким образом, если массив изначально содержал элементы $a_1, a_2, \dots a_{i-1}, a_i, a_{i+1} \dots a_n$ и был выбран $i$-й элемент, то если применить первую операцию, массив станет выглядеть как $a_1, a_2, \dots a_{i-1}, a_{i+1} \dots a_n, a_i,ドル а в случае применения второй операции --- как $a_i, a_1, a_2, \dots a_{i-1}, a_{i+1} \dots a_n$.
Оказалось, что с помощью этих двух операций всегда можно отсортировать массив, что Уолтер и сделал со своим массивом. Но теперь Уолтер дал вам новый массив и попросил найти наименьшее количество таких операций, необходимых, чтобы отсортировать новый массив.
В первой строке содержится одно целое число $n$ --- длина массива, который вам дал Уолтер (1ドル \le n \le 300,000円$).
Во второй строке заданы $n$ целых чисел $a_i,ドル разделенных пробелами --- элементы массива (1ドル \le a_i \le 10^9$).
Выведите единственное число --- минимальное число операций, которые нужно применить к данному массиву, чтобы он стал отсортированным.
5 3 1 2 4 5
2
5 5 4 3 2 1
4
6 2 3 1 6 4 5
2
В первом тесте можно переставить 2ドル$ в начало, а затем 1ドル$ в начало и массив будет отсортирован за две операции.
Во втором тесте можно оставить 5ドル$ на месте, а все остальные элементы по очереди переставить в начало. А можно оставить 1ドル$ на месте, а все остальные элементы переставить в конец. В обоих случаях придется потратить минимум четыре операции.
В третьем тесте достаточно переставить 1ドル$ в начало, а 6ドル$ в конец. Итого две операции.