Sorting of Railcars - A

A train approaches a dead-end from track **1** (refer to the figure). You can detach one or more cars from the front of the train and move them into the dead-end. If desired, the entire train can be moved into the dead-end at once. Afterward, you can move some of these cars out towards track **2**. You can then move additional cars into the dead-end and again move some cars out towards track **2**. This process can be repeated, ensuring each car enters the dead-end from track **1** only once and exits to track **2** only once. Cars cannot enter the dead-end from track **2** or exit to track **1**. Direct movement from track **1** to track **2** without passing through the dead-end is not possible.

The initial order of the train cars is given. Using the allowed operations, you need to arrange the cars in sequential order (starting with car one, then car two, and so on) as the train moves on track **2** away from the dead-end.

Input

The input begins with the number **N** — the total number of cars in the train ((1 $\le$ N $\le$ 2000)). This is followed by the car numbers in the order they appear from the front of the train on track **1** heading towards the dead-end. Each car is uniquely numbered from **1** to **N**.

Output

If it is possible to arrange the cars in order from **1** to **N** as they move on track **2** away from the dead-end, output the sequence of actions required. Each action is described by two numbers: the type of action and the number of cars involved:

• To move **K** cars from track **1** into the dead-end, first output the number **1**, followed by the number **K** ((K $\ge$ 1)).

• To move **K** cars from the dead-end to track **2**, first output the number **2**, followed by the number **K** ((K $\ge$ 1)).

If multiple sequences of actions can achieve the desired result, output any one of them.

If it is impossible to arrange the cars in order, output the single number **0**.

Examples