Airport Sort
Некоторые авиакомпании не назначают номера мест до посадки. Вместо этого каждому пассажиру выдается билет с уникальным целым числом в диапазоне от [1] до [n], где n — это общее количество мест в самолете. Каждый номер билета принадлежит определенной зоне. Если зона содержит k билетов, то билеты с номерами от [1] до [k] находятся в зоне 1; билеты с номерами от [k+1] до [2k] — в зоне 2 и так далее. Последняя зона может содержать меньше k билетов, если n не делится на k.
Перед посадкой все n пассажиров выстраиваются в случайном порядке в одну линию. Чтобы ускорить процесс посадки, желательно, чтобы первые k пассажиров в очереди принадлежали зоне 1, следующие k — зоне 2 и так далее. Существуют два способа перестановки пассажиров.
Соседние пассажиры меняются местами, пока не будет достигнут нужный порядок. Каждую секунду только одна пара соседних пассажиров может поменяться местами.
Все пассажиры одновременно перемещаются к своим правильным местам. Чтобы пройти от позиции x до позиции y, требуется |x-y| секунд, где |x-y| — это абсолютная разница между x и y.
Как вы можете догадаться, первый подход занимает больше времени, но он менее 'шумный'. В этой задаче вам нужно определить, насколько быстрее второй подход. Более конкретно, если минимальное время, необходимое для перестановки пассажиров с использованием первого подхода, равно X, а минимальное время для второго подхода равно Y, вам нужно найти X–Y.
Например, рассмотрим самолет вместимостью 10 (n = 10) и зоны размером 3 (k = 3). Предположим, что пассажиры выстроились в следующем порядке:
3 7 1 2 4 6 5 8 10 9
Каждое целое число представляет номер билета соответствующего пассажира. Таким образом, в приведенном выше примере первый пассажир в очереди имеет билет с номером 3. Пассажиры с номерами билетов 7, 2, 5, 10 и 9 не находятся на своих местах.
Используя первую стратегию, потребуется минимум 6 обменов (и, следовательно, 6 секунд), чтобы достичь желаемого порядка.
I. обмен 7 с 1 => 3 1 7 2 4 6 5 8 10 9
II. обмен 7 с 2 => 3 1 2 7 4 6 5 8 10 9
III. обмен 7 с 4 => 3 1 2 4 7 6 5 8 10 9
IV. обмен 7 с 6 => 3 1 2 4 6 7 5 8 10 9
V. обмен 7 с 5 => 3 1 2 4 6 5 7 8 10 9
VI. обмен 10 с 9 => 3 1 2 4 6 5 7 8 9 10 (теперь все на своих местах)
Используя вторую стратегию, потребуется минимальное время 5 секунд, если мы решим, что окончательный порядок будет (3 2 1 4 6 5 7 8 9 10). Здесь пассажиры с билетами 3, 1 и 8 уже находятся на своих местах; требуется 1 секунда, чтобы пассажиры с билетами 4, 5, 6, 9 и 10 заняли свои места; требуется 2 секунды, чтобы пассажир с билетом 2 занял свое окончательное место; требуется 5 секунд, чтобы пассажир с билетом 7 занял свое место. Это означает, что через 5 секунд все будут на своих местах, используя вторую стратегию. Существуют и другие перестановки, для которых мы получаем 5 секунд, но невозможно придумать что-то меньшее.
Таким образом, вторая стратегия на 1 секунду быстрее.
Входные данные
Первая строка ввода — это целое число T (T < 50), которое указывает количество тестов. Каждый тест состоит из 2 строк. Первая строка содержит 2 положительных целых числа n (n ≤ 20000) и k (k ≤ n). Значения этих переменных указаны выше. Следующая строка содержит n различных целых чисел в диапазоне от [1] до [n]. Первое целое число представляет номер билета пассажира, стоящего в начале очереди.
Выходные данные
Для каждого теста сначала выведите номер теста, а затем требуемый результат (т.е. насколько быстрее второй подход).