eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Поручение мастеру от новичка

Поручение мастеру от новичка

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Думаете, что сортировка это просто? Это не тот случай, когда у Вас нет времени.

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

К счастью, Ваш друг очень хорошо разбирается в сортировке массивов, поэтому Вы решили попросить его о помощи. Вы считаете, что специальные способности Вашего друга обусловлены его концептуальным подходом. За одну секунду он извлекает элемент из массива и помещает его либо в начало, либо в конец массива.

Например, пусть массив имеет вид 4 2 5 6 1 3. Удалив 5 и поставив ее в начало, получим 5 4 2 6 1 3. Если извлечь 2 и поставить ее в конец, то получим 4 5 6 1 3 2.

Конечно, Ваш друг выполняет все операции достаточно быстро, так как не хочет тратить свое время. Единственное, что Вы хотите знать, сколько времени у Вас останется для совершения других полезных дел после сортировки массива.

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

Первая строка содержит количество элементов n (1 n 310^5) в A. Вторая строка содержит n целых чисел A_i (1 A_i10^6).

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

Вывести искомое наименьшее время, за которое Ваш друг отсортирует A в секундах.

Пример

Входные данные #1
5
2 5 1 3 3
Выходные данные #1
2
Автор Геннадий Короткевич
Источник Gennady Korotkevich Contest 1, Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013