Sorting a Three-Valued Sequence

Time Limit:  1 s      Memory Limit:   128 MB
Submission:5     AC:0     Score:99.98


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. (Subtask A). Moreover, construct a sequence of  exchange operations for the respective sorting (Subtask B).


The first line contains the number of records N (1<=N<=1000). Each of the following N lines contains a key value.


Write on the first line the minimal number L of exchange operations needed to make the sequence sorted (Subtask A). 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 (Subtask B). Positions are denoted by the numbers from 1 to N. 


9 2 2 1 3 3 3 2 3 1
4 1 3 4 7 9 2 5 9


IOI1996 Day2