Старий Гусейн#9783

Старий Гусейн

1 секунда

256 мегабайтів

Дуже легка

Гусейн, вже у свої 17 років, відчуває себе старцем і вважає, що йому пора залишити Computer Science. Тому він має завершити всі свої важливі проекти та експерименти. Він майже закінчив усі свої проекти та експерименти, залишився лише один. У нього був чудовий відсортований масив, але після численних експериментів сталося непередбачене: масив перестав бути відсортованим! Здавалося б, що складного в тому, щоб відсортувати масив? Але Гусейн вирішив провести ще один експеримент. Він хоче відсортувати масив, використовуючи лише дві операції:

Взяти будь-який елемент масиву і перемістити його в кінець масиву.
Взяти будь-який елемент масиву і перемістити його на початок масиву.

Таким чином, якщо масив спочатку містив елементи $a_{1}, a_{2}, \dots, a_{i - 1}, a_{i}, a_{i + 1}, \dots, a_{n}$ a_1, a_2, \ldots, a_{i-1}, a_i, a_{i+1}, \ldots, a_n і був обраний $i$ -ий елемент, то після застосування першої операції масив стане $a_{1}, a_{2}, \dots, a_{i - 1}, a_{i + 1}, \dots, a_{n}, a_{i}$ a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n, a_i. А у випадку застосування другої операції - $a_{i}, a_{1}, a_{2}, \dots, a_{i - 1}, a_{i + 1}, \dots, a_{n}$ a_i, a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n. Виявилося, що за допомогою цих двох операцій завжди можна відсортувати масив, що Гусейн і зробив зі своїм масивом. Але тепер Гусейн дав вам новий масив і попросив знайти найменшу кількість таких операцій, необхідних, щоб відсортувати новий масив.

Вхідні дані

У першому рядку міститься одне ціле число $n$ – довжина масиву, який вам дав Гусейн ( $1 \leq n \leq 300000$ 1 \le n \le 300000).

У другому рядку задано $n$ цілих чисел $a_{i}$ a_i, розділених пробілами – елементи масиву ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \le a_i \le 10^9).

Вихідні дані

Виведіть єдине число – мінімальну кількість операцій, які потрібно застосувати до даного масиву, щоб він став відсортованим.

Приклади

Приклад 1

Приклад 2

Приклад 3