Masala #0075
Inversiyalar soni
1 dan N gacha bo’lgan sonlar to’plamining ixtiyoriy permutatsiyasi beriladi. Siz berilgan ketma-ketlikdagi inversiyalar sonini topishingiz kerak.
Inversiyalar soni deb quyidagi shartni qanoatlantiruvchi (i, j) juftliklar soniga aytiladi:
- i < j
- array[i] > array[j]
INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(1 ≤ N ≤ 105) soni kiritiladi. Ikkinchi satrda bo'sh joy bilan ajratilgan holda N ta butun son, 1 dan N gacha bo’lgan sonlarning permutatsiyasi kiritiladi.
OUTPUT.TXT chiqish faylida bitta butun son, masala yechimini chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
10 7 6 2 4 1 5 10 3 9 8 |
19 |
2 |
15 2 7 8 13 11 5 1 9 3 14 4 10 6 12 15 |
38 |
3 |
11 6 10 2 3 9 1 4 7 11 5 8 |
23 |