Арсений работает оператором на сортировочной станции, устройство которой показано на рисунке.
На станции есть входной путь, помеченный на схеме как «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
