Masala H

Xotira 512 MB Vaqt 1000 ms

Tartiblash #2

Sizga N ta quti berilgan bo‘lib, ularning har biri raqamlangan 1 dan N gacha, lekin tartibsiz joylashtirilgan. Siz faqat quyidagi operatsiyani bajara olasiz:

Biror qutini tanlab, uni eng chapga ko‘chirish.

Eng kam amal yordamida qutilarni o‘sish tartibida joylashtirish.

Kiruvchi ma'lumotlar:

Birinchi qatorda N soni beriladi. $(1≤N≤5*10^6)$

Ikkinchi qatorda N ta $a_1,a_2,...,a_n$ tartibsiz sonlar beriladi. $(1≤a_i≤N)$

Chiquvchi ma'lumotlar:

Qutilarni to‘g‘ri tartibga keltirish uchun kerak bo‘lgan minimal amallar sonini chop eting.

Misollar

#	input.txt	output.txt
1	5 3 1 4 2 5	2
2	4 4 3 2 1	3

Izoh:

1-testda.

3 1 4 2 5
↓
2 3 1 4 5
↓
1 2 3 4 5

RoboContest

Masala H

Tartiblash #2