Save the teams
In the olympiad, 2n teams from n different universities participate, with exactly two teams representing each university. All teams are seated in a row at a long table. Sam has noted the initial seating arrangement of the teams.
Yura, known for his strictness, believes a team should be disqualified if it is seated next to another team from the same university. To avoid disqualification and maintain their chances of winning, the teams need to rearrange themselves. They can swap the positions of any two teams (not necessarily adjacent) in one minute.
Your task is to help the teams achieve a seating arrangement in the minimum number of minutes such that no two teams from the same university are seated next to each other. It is guaranteed that this is always possible under the given constraints.
Input
The first line contains the number of universities n (2 ≤ n ≤ 10^5).
The second line contains 2n integers p[1], p[2], ..., p[2n] (1 ≤ p[i] ≤ n), representing the university of the team seated at the i-th position. It is guaranteed that each university has exactly two teams.
Output
On the first line, output the minimum number of minutes k required to achieve the desired seating arrangement.
In each of the following k lines, output two integers a[i] and b[i] (1 ≤ a[i], b[i] ≤ 2n), indicating the positions of the teams that swap places in the i-th minute.
If there are multiple possible solutions, you may output any of them.