Старий Гусейн
Гусейн, вже у свої 17 років, відчуває себе старцем і вважає, що йому пора залишити Computer Science. Тому він має завершити всі свої важливі проекти та експерименти. Він майже закінчив усі свої проекти та експерименти, залишився лише один. У нього був чудовий відсортований масив, але після численних експериментів сталося непередбачене: масив перестав бути відсортованим! Здавалося б, що складного в тому, щоб відсортувати масив? Але Гусейн вирішив провести ще один експеримент. Він хоче відсортувати масив, використовуючи лише дві операції:
Взяти будь-який елемент масиву і перемістити його в кінець масиву.
Взяти будь-який елемент масиву і перемістити його на початок масиву.
Таким чином, якщо масив спочатку містив елементи a[1], a[2], ..., a[i-1], a[i], a[i+1], ..., a[n] і був обраний i-ий елемент, то після застосування першої операції масив стане a[1], a[2], ..., a[i-1], a[i+1], ..., a[n], a[i]. А у випадку застосування другої операції - a[i], a[1], a[2], ..., a[i-1], a[i+1], ..., a[n]. Виявилося, що за допомогою цих двох операцій завжди можна відсортувати масив, що Гусейн і зробив зі своїм масивом. Але тепер Гусейн дав вам новий масив і попросив знайти найменшу кількість таких операцій, необхідних, щоб відсортувати новий масив.
Вхідні дані
У першому рядку міститься одне ціле число n – довжина масиву, який вам дав Гусейн (1 <= n <= 300000).
У другому рядку задано n цілих чисел a[i], розділених пробілами – елементи масиву (1 <= a[i] <= 10^9).
Вихідні дані
Виведіть єдине число – мінімальну кількість операцій, які потрібно застосувати до даного масиву, щоб він став відсортованим.