### 8th International Olympiad in Informatics, Veszprém, Hungary

# IOI'96 Day 2

Problem 1: Sorting a Three-Valued Sequence

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).

### Input Data

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.

### Output Data

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.

### Example Input and Output

*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

*Figure 1*