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\[i\]10^6).

Вихідні дані

Вивести шуканий найменший час, за який Ваш друг відсортує A в секундах.

Приклад

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