28757번 - Починка массива 다국어

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

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

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

Таким образом, если массив изначально содержал элементы $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$ в конец. Итого две операции.