Muallif: __thecrash__
E. Minimal almashtirishlar soni
Vaqt limiti: 2000 ms Xotira limiti: 256 mb
Sizga \(n\) ta sondan iborat \(a_1, a_2, \dots, a_n\) massiv berilgan (barcha elementlar turlicha). Bitta amalda siz massivdagi ixtiyoriy ikkita elementning o'rnini almashtira olasiz. Sizning vazifangiz — massivni o'sish tartibiga keltirish uchun zarur bo'ladigan eng kam almashtirishlar sonini topishdan iborat.
Kiruvchi ma'lumotlar
Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 10^5\)) — massivdagi elementlar soni beriladi. Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) beriladi, bo'sh joy bilan ajratilgan. Barcha \(a_i\) qiymatlari o'zaro turlicha ekanligi kafolatlanadi.
Chiquvchi ma'lumotlar
Yagona qatorda bitta butun son — massivni saralash uchun zarur bo'ladigan eng kam almashtirishlar sonini chiqaring.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
4 4 3 2 1 |
2 |
2 |
5 2 3 4 5 1 |
4 |
Izoh
Berilgan \([4, 3, 2, 1]\) massivini saralash uchun \(2\) ta almashtirish yetarli: avval \(4\) va \(1\) ni almashtiramiz — \([1, 3, 2, 4]\), so'ng \(3\) va \(2\) ni almashtiramiz — \([1, 2, 3, 4]\).