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