Починка массива

У Уолтера Беккета был замечательный отсортированный массив, однако, после множества экпериментов произошло непредвиденное: а именно, массив перестал быть отсортированным!

Казалось бы, что сложного в том, чтобы отсортировать массив? Но Уолтер и здесь решил провести эксперимент. Он хочет отсортировать массив используя только две операции:

• Взять любой элемент массива и переместить его в конец массива.
• Взять любой элемент массива и переместить его в начало массива.

Таким образом, если массив изначально содержал элементы $a\_1, a\_2, \dots a\_{i-1}, a\_i, a\_{i+1} \dots a\_n$ и был выбран $i$-й элемент, то если применить первую операцию, массив станет выглядеть как $a\_1, a\_2, \dots a\_{i-1}, a\_{i+1} \dots a\_n, a\_i$, а в случае применения второй операции --- как $a\_i, a\_1, a\_2, \dots a\_{i-1}, a\_{i+1} \dots a\_n$.

Оказалось, что с помощью этих двух операций всегда можно отсортировать массив, что Уолтер и сделал со своим массивом. Но теперь Уолтер дал вам новый массив и попросил найти наименьшее количество таких операций, необходимых, чтобы отсортировать новый массив.

В первой строке содержится одно целое число $n$ --- длина массива, который вам дал Уолтер ($1 \le n \le 300\\,000$).

Во второй строке заданы $n$ целых чисел $a\_i$, разделенных пробелами --- элементы массива ($1 \le a\_i \le 10^9$).

Выведите единственное число --- минимальное число операций, которые нужно применить к данному массиву, чтобы он стал отсортированным.

В первом тесте можно переставить $2$ в начало, а затем $1$ в начало и массив будет отсортирован за две операции.

Во втором тесте можно оставить $5$ на месте, а все остальные элементы по очереди переставить в начало. А можно оставить $1$ на месте, а все остальные элементы переставить в конец. В обоих случаях придется потратить минимум четыре операции.

В третьем тесте достаточно переставить $1$ в начало, а $6$ в конец. Итого две операции.