На бесконечно длинном железнодорожном пути стоит состав из n вагонов, пронумерованных от 1 до n (номера всех вагонов различны) и предварительно перемешанных. Дэвид Блейн хочет отсортировать вагоны по возрастанию их номеров. За одно действие он может заставить один из вагонов исчезнуть со своего места и телепортировать его либо в начало состава, либо в конец, по своему усмотрению. Какое минимальное количество действий потребуется Дэвиду Блейну, чтобы отсортировать состав?
Выходные данные
Выведите целое число — минимальное количество действий, необходимое для сортировки вагонов.
Примечание
В первом примере можно сначала телепортировать 4-й вагон, а затем 5-й вагон в конец состава.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 1 2 5 3
|
2
|
|
2
|
4
4 1 3 2
|
2
|