IOI '96 - Veszprém, Hungary

Sorting is one of the most frequently done computational tasks. Consider the special sorting problem, where the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers ~1~, ~2~ and ~3~. The required sorting order is non-decreasing. Sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers ~p~ and ~q~, exchanges the elements in positions ~p~ and ~q~.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted. Moreover, construct a sequence of exchange operations for the respective sorting.

Input Specification

The first line of input contains the number of records ~N~ ~(1 \le N \le 1\,000)~. Each of the following ~N~ lines contains a key value.

Output Specification

The first line of output should contain the minimal number ~L~ of exchange operations needed to make the sequence sorted. The following ~L~ lines give the respective sequence of the exchange operations in the order performed. Each line contains one exchange operation described by two numbers ~p~ and ~q~, the positions of the two elements to be exchanged. Positions are denoted by the numbers from ~1~ to ~N~.

Note: The answer is not necessarily unique. Your program is only required to find one possible sequence of exchanges.

Sample Input

9
2
2
1
3
3
3
2
3
1

Sample Output

4
1 3
4 7
9 2
5 9