Бартек — известный продюсер техно-музыки, и сейчас он доводит до совершенства свой следующий хит. Он создал трек, состоящий из $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$.