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

# IOI'96 Day 2

Problem 1: Sorting a Three-Valued Sequence

Return to Task Overview
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*