Mincraft ~2.0~ has finally come out! The major updates include:

• Inventory reduced to ~3~ slots
• Increased the storage of each slot to ~2000~ items
• Slots can now contain distinct items

Everybody was excited for the new update, as inventory management was now extremely inefficient simple! Players can only use a single mouse movement to organize items in their inventory one at a time. Formally, a mouse movement consists of picking up an item from the top of inventory slot ~1~ or ~2~ and moving it to the top of any other slot. Oddly, items from slot ~3~ can't be moved!

Soon after Mincraft ~2.0~ released, Tinyfold began speedrunning to get to the top of the leaderboards. He is currently three minutes into his run and is already stacked. However, all the loot he got from a bastion is unorganized in slot ~1~ of his inventory. Given the permutation ~p_1, p_2, \dots, p_N~ representing the items in slot ~1~ from bottom to top, please tell Tinyfold how he should move his mouse so that all his items are sorted in ascending order from bottom to top in slot ~3~. Since he is speedrunning, you should give him a minimal sequence of mouse movements.

Constraints

~1 \le N \le 2000~
~1 \le p_i \le N~

It is guaranteed that ~p_1, p_2, \dots, p_N~ is a permutation of the integers from ~1~ to ~N~.

Input Specification

The first line will contain a positive integer ~N~.

The next line will contain ~N~ integers ~p_1, p_2, \dots, p_N~ representing the permutation of slot ~1~ from bottom to top.

Output Specification

The first line should contain one integer, the minimum number of mouse movements. Then, for each mouse movement, output one line containing the slot number of the item that is being moved, followed by a space, followed by the destination slot number. If there are multiple minimal sequences of mouse movements, output any one of them.

Sample Input 1

3
2 1 3

Sample Output 1

4
1 2
1 3
1 3
2 3

Explanation for Sample 1

Initially, Tinyfold's inventory is as follows (items are ordered from bottom to top in each slot):

Slot 1: 2 1 3
Slot 2: 
Slot 3:

The first mouse movement, 1 2, moves the item at the top of slot ~1~ (item ~3~) to the top of slot ~2~:

Slot 1: 2 1
Slot 2: 3
Slot 3:

The second mouse movement, 1 3, moves the item at the top of slot ~1~ (item ~1~) to the top of slot ~3~:

Slot 1: 2
Slot 2: 3
Slot 3: 1

The third mouse movement, 1 3, moves the item at the top of slot ~1~ (item ~2~) to the top of slot ~3~:

Slot 1: 
Slot 2: 3
Slot 3: 1 2

The fourth mouse movement, 2 3, moves the item at the top of slot ~2~ (item ~3~) to the top of slot ~3~:

Slot 1: 
Slot 2: 
Slot 3: 1 2 3

Now, Tinyfold's items are sorted in ascending order from bottom to top in slot ~3~! It can be shown that ~4~ mouse movements is minimal.

Sample Input 2

5
3 5 2 4 1

Sample Output 2

8
1 3
1 2
1 3
1 2
1 3
2 1
2 3
1 3