Masala #0358

Insertion sort algoritmi barchaga ma’lum. Shunday bo’lsada yanam bir bor eslatib o’tamiz:

n uzunlikdagi massivni kamaymaydigan tartibda saralash uchun:

1. arr[1] dan arr[n] gacha barcha element birma-bir yurib chiqiladi;
2. Joriy element o’zidan oldingilar bilan solishtiriladi;
3. Joriy elementdan katta bo’lgan barcha elementlar bir pog’ona o’ngga suriladi, bo’sh qolgan joyga joriy element joylashtiriladi.

Misol uchun: 4 3 2 10 12 1 5 6 ketma-ketlikdagi massiv quyidagi ketma-ketlikda saralanadi:

Bu saralash algoritmida asosiy vaqt elementlarni surish uchun ketadi. Jami surishlar soni yuqoridagi jadvalda qizil rang bilan ko’rsatilgan kataklar soniga teng bo’lishi bizga ma’lum.

Siz n ta elementdan iborat arr massivi uchun Insertion sort algoritmi necha marotaba surish amalini ishlatishini aniqlang.

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 15)\) testlar soni kiritiladi. Ikkinchi satrdan boshlab, har bir test uchun alohida ikkita satrning birinchi satrida \(n (1 \le n \le 100000)\), massiv elementlari soni, ikkinchi satrida n ta butun son, \(arr (1 \le arr_i \le 10000000)\) massiv elementlari kiritiladi.

Har bir test uchun alohida satrda bitta butun son, masala yechimini chop eting