Masala #0085

Xotira 16 MB Vaqt 1000 ms
14

Insertion sort

Insertion sort algoritmi oddiy saralash algoritmlari safida turadi. Ba’zida berilgan massivni saralash uchun insertion sort juda ko’p vaqt talab qilishi kuzatiladi. Ammo insertion sortda elementlarni surishlar sonini topishning boshqacha usullari ham mavjud.

Agar k[i] massivning i-elementi siljishi kerak bo’lgan elementlar soni bo’lsa, unda umumiy siljishlar soni k[1]+k[2]+k[3]+…+k[n] ga teng bo’ladi. Misol uchun massiv arr=[4,3,2,1] bo’lsa.

Massiv

Surishlar soni

[4,3,2,1]

 

[3,4,2,1]

1

[2,3,4,1]

2

[1,2,3,4]

3

Umumiy surishlar soni=1+2+3=6


Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1≤T≤15) testlar soni kiritiladi.

Keyin har bir test uchun alohida ikkita qatorning birinchi satrida N(1≤N≤100000) massiv elementlari soni, ikkinchi satrida esa N ta butun son, massiv elementlari kiritiladi. (1 ≤ a[i] ≤ 10000000)


Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida satrda bittadan butun son, umumiy surishlar sonini chop eting.


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