Adrenaline Rush

Alice's friend is a big fan of the Adrenaline Rush racing competition and tries to attend every race. This time, Alice is the one watching. So that her friend misses no important details, Alice decides to note everything that happens on the track.

Before the race starts, the first thing Alice notices is the car numbering. All cars line up in front of the starting line in a fixed order. The car closest to the line is numbered $1$, the second car is numbered $2$, and so on up to the last car, $n$. How convenient, Alice thinks.

The race begins with a countdown: "Three! Two! One! Go!" Alice sees the cars start in their original order. As the race goes on, the order changes. Each time one car overtakes another, the two swap places on the track, and Alice records it.

Alice notices something unusual during the race. No car overtakes another car more than once. For any two cars $x$ and $y$, at most two overtakes happen between them: "$x$ overtakes $y$" and/or "$y$ overtakes $x$".

At the end, Alice carefully writes the final order $c_1, c_2, \ldots, c_n$, where $c_1$ is the winner.

Alice's friend only cares about the final ranking and throws away all of Alice's notes except that order. Alice is curious, though. What is the longest possible sequence of overtakes she could have observed? Help her find out.

The first line contains a single integer $n$ ($1 \le n \le 1000$), the number of cars.

The second line contains a permutation $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$, $c_i \ne c_j$), the final order of the cars.

The first line of the output is a single integer $m$, the maximum possible number of overtakes.

Each of the next $m$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$), meaning car $x$ overtakes car $y$. At the moment of the overtake, car $x$ is directly behind car $y$. List the overtakes in the order they occur.

After all $m$ overtakes, the cars must finish in the order $c_1, c_2, \ldots, c_n$. No car $x$ may overtake the same car $y$ more than once. If several longest sequences exist, output any of them.