A. Сортировка вагонов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 100 000) — количество вагонов в составе.

Во второй строке записаны n целых чисел pi (1 ≤ pi ≤ n, pi ≠ pj при i ≠ j) — последовательность номеров вагонов в составе.

Выходные данные

Выведите целое число — минимальное количество действий, необходимое для сортировки вагонов.

Примеры
Входные данные
5
4 1 2 5 3
Выходные данные
2
Входные данные
4
4 1 3 2
Выходные данные
2
Примечание

В первом примере можно сначала телепортировать 4-й вагон, а затем 5-й вагон в конец состава.