eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Old Huseyn

Old Huseyn

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
image.jpg

Гусейн уже в свои 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 ) .

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

Пример

Входные данные #1
5
3 1 2 4 5
Выходные данные #1
2
Входные данные #2
5
5 4 3 2 1
Выходные данные #2
4
Входные данные #3
6
2 3 1 6 4 5
Выходные данные #3
2
Источник Интернет-олимпиады, Сезон 2019-2020, Первая личная олимпиада, Университет ИТМО,26 января 2020 . CoronaVirus GrandPrix 2020 Round 3.