Бартек — відомий продюсер техно-музики, і зараз він доводить до досконалості свій наступний хіт. Він створив трек, що складається з $n$ бітів (тактів), пронумерованих поспіль від $1$ до $n$. Провівши багато годин у програмі для редагування музики, він уже збирався експортувати mp3-файл, але помітив, що біти наразі розташовані в порядку $a_1, a_2, \dots, a_n$. Бартеку потрібно розташувати біти в порядку зростання, тобто $1, 2, \dots, n$.

Програма дозволяє виконувати операції двох типів:

• Перемістити останній біт на будь-яку позицію, наприклад $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Перемістити будь-який біт на початок, наприклад $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Яка мінімальна кількість операцій необхідна, щоб розташувати біти в порядку зростання?

Вхідні дані

Перший рядок містить ціле число $n$ ($1 \le n \le 200\,000$), що позначає кількість бітів.

Другий рядок містить $n$ попарно різних цілих чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), що представляють поточний порядок бітів у програмі.

Вихідні дані

Виведіть одне ціле число — мінімальну необхідну кількість операцій.

Приклади

Вхідні дані 1

6
3 2 5 4 1 6

Вихідні дані 1

4

Вхідні дані 2

9
3 1 2 5 6 4 9 7 8

Вихідні дані 2

6

Примітка

Ми починаємо з послідовності бітів $(3, 2, 5, 4, 1, 6)$. Ось один зі способів отримати бажаний порядок за чотири операції:

• Перемістити останній біт на дві позиції вліво: $(3, 2, 5, \underline{6}, 4, 1)$.
• Перемістити біт $2$ на початок: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Перемістити біт $1$ на початок: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Перемістити останній біт на дві позиції вліво: $(1, 2, 3, \underline{4}, 5, 6)$.

Отримати зростаючий порядок за чотири операції можна й іншими способами, але за три операції це зробити неможливо, тому результат дорівнює $4$.