Masala #0085

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.

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)

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