eolymp
bolt
Try our new interface for solving problems
Məsələlər

Сортировщик поезда

Сортировщик поезда

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

На старой железнодорожной станции Вы все еще можете столкнуться с одним из последних оставшихся "сортировщиков поездов". Сортировщик поезда - это работник железной дороги, единственной задачей которого является перестановка вагонов поездов. После того, как вагоны расположены в правильном порядке, все, что нужно будет сделать машинисту поезда, это сбросить вагоны, один за другим, на станциях, для которых предназначен груз.

Название "сортировщик поезда" происходит от первого человека, который выполнил эту задачу, на станции, расположенной рядом с железнодорожным мостом. Вместо вертикального открытия мост вращался вокруг колонны в центре реки. Повернув мост на 90 градусов, лодки могут пройти влево или вправо.

Первый сортировщик поезда обнаружил, что мост может эксплуатироваться максимум с двумя вагонами на нем. Повернув мост на 180 градусов, вагоны поменялись местами, что позволило ему переставить вагоны (как побочный эффект, вагоны затем повернулись в противоположном направлении, но вагоны поезда могут двигаться в любом направлении, так что кого это волнует).

Теперь, когда почти все железнодорожные сортировщики вымерли, железнодорожная компания хотела бы автоматизировать их работу. Частью программы, которая должна быть разработана, является процедура, которая определяет для данного поезда наименьшее количество перестановок местами двух смежных вагонов, необходимых для приведения в порядок поезда. Ваше задание - создать такую программу.

prb8735.gif

Giriş verilənləri

Содержит в первой строке количество тестов n. Каждый тест состоит из двух строк. Первая строка теста содержит целое число l (0l10000), определяющее длину поезда. Вторая строка теста содержит перестановку чисел от 1 до l, указывающих текущий порядок вагонов. Вагоны должны быть упорядочены таким образом, чтобы вагон 1 шел первым, затем вагон 2 и так далее. Вагон l должен идти последним.

Çıxış verilənləri

Для каждого теста выведите предложение: "Optimal train swapping takes s swaps.", где s - целое число.

Nümunə

Giriş verilənləri #1
3
3
1 3 2
4
4 3 2 1
2
2 1
Çıxış verilənləri #1
Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.