B. Починка массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Уолтера Беккета был замечательный отсортированный массив, однако, после множества экпериментов произошло непредвиденное: а именно, массив перестал быть отсортированным!

Казалось бы, что сложного в том, чтобы отсортировать массив? Но Уолтер и здесь решил провести эксперимент. Он хочет отсортировать массив используя только две операции:

  • Взять любой элемент массива и переместить его в конец массива.
  • Взять любой элемент массива и переместить его в начало массива.
Таким образом, если массив изначально содержал элементы $$$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$$$).

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

Выведите единственное число — минимальное число операций, которые нужно применить к данному массиву, чтобы он стал отсортированным.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
110$$$n \le 10$$$полная
210$$$n \le 300$$$ и все $$$a_i$$$ — различныпервая ошибка
315$$$n \le 5\,000$$$ и все $$$a_i$$$ — различны2первая ошибка
420Все $$$a_i$$$ — различны2, 3первая ошибка
510$$$n \le 300$$$1, 2первая ошибка
615$$$n \le 5\,000$$$1, 2, 3, 5первая ошибка
720Без дополнительных ограничений1, 2, 3, 4, 5, 6первая ошибка
Примеры
Входные данные
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$$$ в конец. Итого две операции.