Old Huseyn
Гусейн уже в свои 17 лет чувствует себя стариком и считает ,что ему уже пора уходить из Computer Science.Поэтому он должен завершить все свои важные проекты и эксперименты. Он почти завершил все свои проекты и эксперименты и остался только один из них.У него был замечательный отсортированный массив,однако после множества экспериментов произошло непредвиденное : а именно массив перестал быть отсортированным ! Казалось бы ,что сложного в том ,чтобы отсортировать массив ? Но Гусейн решил провести еще одинэксперимент . Он хочет отсортировать массив используя только две операции:
Взять любой элемент массива и переместить его в конец массива.
Взять любой элемент массива и переместить его в начало массива.
Таким образом ,если массив изначально содержал элементы a[1],a[2],....,a[i-1],a[i],a[i+1],.....,a[n] и был выбран i-ыйэлемент ,то если применить первую операцию, массивстанет как a[1] , a[2] , .... , a[i-1] , a[i+1] ,....., a[n] , a[i] . А в случаеприменения второй операции - как a[i],a[1] , a[2] ,...., a[i-1] , a[i+1] , ..... , a[n] .Оказалось ,что с помощью этих двух операций всегда можно отсортировать массив ,что Гусейн и сделал сосвоим массивом. Но теперь Гусейн дал вам новый массив и попросил найти наименьшее количество такихопераций ,необходимых ,чтобы отсортировать новый массив .
####Входные данныеВ первой строке содержится одно целое число n – длинамассива , который вам дал Гусейн (1 <= n <= 300000) .
Во второй строке заданы n целых чисел a[i] разделенныхпробелами – элементы массива ( 1 <= a[i] <= 10^9 ) .
####Выходные данныеВыведите единственное число – минимальное число операций ,которые нужно применить к данномумассиву ,чтобы он стал отсортированным .