Доручення для майстра від новачка
Думаєте, що сортування це просто? Це не той випадок, коли у Вас немає часу.
Несподівані дивні речі часто трапляються у нашому житті. Наприклад, у Вас є масив А, який необхідно упорядкувати за неспаданням. Проблема у тому, що у Вас дійсно немає на це часу.
На щастя, Ваш друг дуже добре розбирається у сортуванні масивів, тому Ви вирішили попросити його про допомогу. Ви вважаєте, що спеціальні здібності Вашого друга обумовлені його концептуальним підходом. За одну секунду він дістає елемент з масиву і поміщає його або на початок, або у кінець масиву.
Наприклад, нехайь масив маєт вигляд 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 в секундах.