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

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

Таким образом ,если массив изначально содержал элементы a1,a2,....,ai1,ai,ai+1,.....,an и был выбран i-ый элемент ,то если применить первую операцию, массив станет как a1 , a2 , .... , ai-1 , ai+1 ,....., an , ai . А в случае применения второй операции - как ai,a1 , a2 ,...., ai-1 , ai+1 , ..... , an . Оказалось ,что с помощью этих двух операций всегда можно отсортировать массив ,что Гусейн и сделал со своим массивом. Но теперь Гусейн дал вам новый массив и попросил найти наименьшее количество таких операций ,необходимых ,чтобы отсортировать новый массив .

Входные данные

В первой строке содержится одно целое число n – длина массива , который вам дал Гусейн (1 <= n <= 300000) .

Во второй строке заданы n целых чисел ai разделенных пробелами – элементы массива ( 1 <= ai <= 109 ) .

Выходные данные

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