Манхеттенське сортування
Ще одна задача на сортування! У цій задачі вам надано послідовність S з N різних цілих чисел, і вам потрібно відсортувати її з мінімальною вартістю, використовуючи лише одну операцію:
Манхеттенський обмін!
Нехай S_i та S_j — це два елементи послідовності на позиціях i та j відповідно. Застосування операції манхеттенського обміну до S_i та S_j змінює місцями обидва елементи з вартістю |i-j|. Наприклад, для послідовності {9, 5, 3} ми можемо відсортувати послідовність за допомогою однієї операції манхеттенського обміну, змінивши місцями перший і останній елементи з загальною вартістю 2 (абсолютна різниця між позиціями 9 та 3).
Вхідні дані
Перша строка вхідних даних містить ціле число T, кількість тестових випадків. Кожен тестовий випадок складається з 2 рядків. Перший рядок містить одне ціле число (1 ≤ N ≤ 30), довжину послідовності S. Другий рядок містить N цілих чисел, розділених пробілами, що представляють елементи S. Усі елементи послідовності є різними і вміщуються в 32-бітне знакове ціле число.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить одне ціле число, мінімальну вартість сортування послідовності, використовуючи лише операцію манхеттенського обміну.