Поручение мастеру от новичка
Поручение мастеру от новичка
Думаете, что сортировка это просто? Это не тот случай, когда у Вас нет времени.
Неожиданные странные вещи часто случаются в нашей жизни. Например, у Вас имеется массив А, который необходимо упорядочить по неубыванию. Проблема в том, что у Вас действительно нет на это времени.
К счастью, Ваш друг очень хорошо разбирается в сортировке массивов, поэтому Вы решили попросить его о помощи. Вы считаете, что специальные способности Вашего друга обусловлены его концептуальным подходом. За одну секунду он извлекает элемент из массива и помещает его либо в начало, либо в конец массива.
Например, пусть массив имеет вид 4 2 5 6 1 3. Удалив 5 и поставив ее в начало, получим 5 4 2 6 1 3. Если извлечь 2 и поставить ее в конец, то получим 4 5 6 1 3 2.
Конечно, Ваш друг выполняет все операции достаточно быстро, так как не хочет тратить свое время. Единственное, что Вы хотите знать, сколько времени у Вас останется для совершения других полезных дел после сортировки массива.
Входные данные
Первая строка содержит количество элементов n (1 ≤ n ≤ 3∙10^5) в A. Вторая строка содержит n целых чисел A_i (1 ≤ A_i ≤ 10^6).
Выходные данные
Вывести искомое наименьшее время, за которое Ваш друг отсортирует A в секундах.
Пример
5 2 5 1 3 3
2