Манхэттенская сортировка
Ещё одна задача на сортировку! В этой задаче вам дана последовательность 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-битное знаковое целое число.
Выходные данные
Для каждого теста выведите одну строку, содержащую одно целое число, минимальную стоимость сортировки последовательности, используя только операцию манхэттенского обмена.