Задача №114963. Железнодорожная сортировка
Арсений работает оператором на сортировочной станции.
На станции есть входной путь, помеченный на схеме как « input », выходной путь, помеченный на схеме как « output » и два тупика. Оператор может перемещать вагоны между путями и тупиками, используя следующие операции.
Если вагон \(x\) является первым вагоном на входном пути справа от тупиков, этот вагон можно переместить в любой тупик. Команда « 1 » перемещает вагон в тупик \(1\), а команда « 2 » перемещает вагон в тупик \(2\).
Если вагон \(x\) — ближайший к выезду вагон в одном из тупиков, его можно переместить в выходной путь слева от тупиков. Команда « -1 » перемещает вагон из тупика \(1\), а команда « -2 » перемещает вагон из тупика \(2\).
Наконец, можно перемещать вагоны между тупиками, если \(x\) — ближайший к выезду вагон в одном из тупиков, его можно переместить в другой тупик. Команда « 12 » перемещает вагон из тупика \(1\) в тупик \(2\), а команда « 21 » перемещает вагон из тупика \(2\) в тупик \(1\).
Обратите внимание, что вагоны не могут быть возвращены в тупик с выходного пути слева от сортировочной станции и не может быть возвращен из тупика на входной путь справа сортировочной станции. Также нельзя проводить вагон напрямую с входного пути на выходной путь, требуется использовать тупик. Оба тупика могут содержать произвольное число вагонов.
Справа на станцию прибывает состав из \(n\) вагонов, каждый вагон имеет номер от 1 до \(n\), разные вагоны имеют разные номера.
Арсений должен отсортировать вагоны, чтобы они все находились на выходном пути и их номера слева направо шли по возрастанию. Помогите ему сформировать последовательность команд, которая позволит этого добиться. Количество команд в последовательности не должно превышать \(2 \cdot 10^6\).
Первая строка ввода содержит число \(n\) — количество вагонов (\(1 \le n \le 1000\)).
Вторая строка содержит \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — номера вагонов в порядке слева направо, в котором находятся на входном пути.
Выведите последовательность команд, которая приведет к тому, что вагоны будут находиться на выходном пути и их номера будут идти по возрастанию. Последовательность должна содержать не более \(2 \cdot 10^6\) команд.
Если есть несколько подходящих последовательностей, можно вывести любую из них.
Гарантируется, что для любых входных данных существует последовательность команд, содержащая не более \(2 \cdot 10^6\) команд.
5 3 1 5 2 4
1 1 -1 1 1 -1 12 -1 1 -1 -2