Snowboarding
The weather during the initial days of the Olympics was disappointing for both athletes and spectators. However, the organizers faced the greatest challenges. Heavy rain and warm temperatures destroyed much of the snow on the snowboard track. Consequently, the organizers had to postpone the competitions several times while attempting to restore the track using snow reserves.
When everything was finally ready for the start, it was discovered that the rain had washed away all the standing areas in the competition arena. The organizers incurred significant losses and were forced to sell tickets only for the first row of seats—the sole row available.
On the day of the competition, each of the N spectators who purchased tickets for the first row took a seat there. However, upon checking the tickets, it was found that none of the spectators were in their assigned seats, although all seats were occupied. In one step, a volunteer can swap two adjacent spectators if neither is sitting in their assigned seat. If a spectator is already in their assigned seat, they cannot be moved, as it would obstruct their view of the competition. Your task is to help arrange the seating so that all spectators are in their assigned seats. Act quickly, as the most exciting performances are about to begin.
Input
The first line contains an integer N (2 ≤ N ≤ 300). The second line contains N numbers—a permutation from 1 to N—representing the initial seating arrangement of the spectators. It is guaranteed that no spectator is initially sitting in their assigned seat.
Output
If a solution does not exist, output -1. Otherwise, on the first line, output the number of steps required to arrange the seating. Then, output each step on a separate line. A step is described by two numbers indicating the positions of the spectators who are swapped in that step. The number of steps should not exceed 45000. If there are multiple solutions, you may output any one of them.