Old Huseyn
Old Huseyn
Гусейн уже в свои 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
) .
Выходные данные
Выведите единственное число – минимальное число операций ,которые нужно применить к данному массиву ,чтобы он стал отсортированным .
5 3 1 2 4 5
2
5 5 4 3 2 1
4
6 2 3 1 6 4 5
2