Masala #VMEIVEHUY7
Swap
Sizga ixtiyoriy sonlar massivi a berilgan. Siz bu massivda bir qator almashtirish (swap) operatsiyalarini bajarish orqali barcha elementlarni 1 dan n gacha bo'lgan natural sonlar ko'rinishiga keltirishingiz kerak. Ammo almashtirishlar faqat massivdagi o'zaro qo'shni bo'lgan elementlar orasida bajarilishi mumkin. Sizning vazifangiz bu jarayonni bajarish uchun kerak bo'lgan minimal almashtirishlar sonini aniqlash.
Birinchi qatorda butun son n (1 ≤ n ≤ 100,000) – massivning o'lchami.
Ikkinchi qatorda n ta butun son a[i] (1 ≤ a[i] ≤ n) – elementlar, bu elementlar 1 dan n gacha bo'lgan qiymatlar to'plamidan iborat, ammo tartibsiz ko'rinishda.
Minimal almashtirishlar sonini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 3 5 4 1 2 |
5 |
Massivni tartiblangan ko'rinishga keltirish uchun minimal almashtirishlar jarayoni quyidagicha bo'lishi mumkin:
- [3 5 4 1 2] → [3 4 5 1 2] → [3 4 1 5 2] → [3 1 4 5 2] → [1 3 4 5 2] → [1 3 4 2 5] → [1 2 3 4 5]
Bu jarayonda jami 5 ta almashtirish amalga oshirildi.
Telegram kanalimizga obuna bo'ling