Arsenii 在一个调车场工作，其布局如图所示。

该车站有一个输入轨道、一个输出轨道和两个尽头线（死胡同）。操作员可以在轨道和尽头线之间移动车辆。

如果车辆 $x$ 是输入轨道上的第一辆车，它可以被移动到任意一个尽头线。指令 "1" 将车辆移动到尽头线 1，指令 "2" 将车辆移动到尽头线 2。

如果车辆 $x$ 是某个尽头线中距离出口最近的车辆，它可以被移动到输出轨道。指令 "-1" 将车辆从尽头线 1 移出，指令 "-2" 将车辆从尽头线 2 移出。

最后，你可以在尽头线之间移动车辆。如果 $x$ 是某个尽头线中距离出口最近的车辆，它可以被移动到另一个尽头线。指令 "12" 将车辆从尽头线 1 移动到尽头线 2，指令 "21" 将车辆从尽头线 2 移动到尽头线 1。

请注意，车辆不能从输出轨道返回到尽头线，也不能从尽头线返回到输入轨道。此外，你不能直接将车辆从输入轨道移动到输出轨道，必须经过尽头线。两个尽头线都可以容纳任意数量的车辆。

一列包含 $n$ 节车厢的火车到达输入轨道，每节车厢都有一个从 $1$ 到 $n$ 的唯一编号。

Arsenii 必须对这些车厢进行排序，使得它们全部位于输出轨道上，且从左到右的编号呈升序排列。请帮助他生成一个指令序列来实现这一目标。序列中的指令数量不得超过 $2 \cdot 10^6$。

输入格式

第一行包含一个整数 $n$ —— 车厢的数量 ($1 \le n \le 1000$)。

第二行包含 $n$ 个不同的整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) —— 输入轨道上从左到右的车厢编号。

输出格式

打印一个指令序列，使得车厢最终位于输出轨道上，且编号呈升序。该序列包含的指令数量不得超过 $2 \cdot 10^6$。

如果存在多个正确的序列，你可以输出其中任意一个。

题目保证对于任何输入数据，都存在一个长度不超过 $2 \cdot 10^6$ 的指令序列。

样例

输入 1

5
3 1 5 2 4

输出 1

1
1
-1
1
1
-1
12
-1
1
-1
-2