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 of file INPUT.TXT contains the number of records N (1<=N<=1000). Each of the following N lines contains a key value.
Write on the first line of file OUTPUT.TXT 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.
Figure 1 gives an input file and a corresponding output file.
INPUT.TXT OUTPUT.TXT 9 4 2 1 3 2 4 7 1 9 2 3 5 9 3 3 2 3 1