Bob is sitting through another session of physics class, with a topic regarding the force of gravity on an object. Bob thinks that the force of gravity is the same for all objects, regardless of their mass. However, his teacher Dr. Henri knows better. To convince Bob that he is wrong, Dr. Henri dug up ~2N~ weights (the ~i~-th weight having mass ~m_i~ grams) and ~N~ balance scales (the traditional kind with plates to the left and right of the fulcrum).
Dr. Henri knows that the scales will tip to the plate holding a higher mass, or remain balanced if the masses on both sides are equal. To be as convincing as possible, Dr. Henri would like to arrange the ~2N~ weights on the ~N~ scales with exactly one weight on each plate of each scale such that the maximum number of scales are tipped to either side. Please find an arrangement of the weights satisfying this requirement.
~1 \le N \le 5 \times 10^5~
~1 \le m_i \le 10^9~
Subtask 1 [20%]
~1 \le m_i \le 2~
Subtask 2 [30%]
~1 \le N \le 2 \times 10^3~
Subtask 3 [50%]
No additional constraints.
The first line contains an integer ~N~.
The second line contains ~2N~ space-separated integers ~m_i~ ~(1 \le i \le 2N)~, the masses of the weights.
On the first line output an integer ~M~, the maximum possible number of tipped scales.
On the ~j~-th of the next ~N~ lines, output ~2~ space-separated integers ~a_j~ and ~b_j~ ~(1 \le a_j, b_j \le 2N)~, representing that the ~j~-th scale holds the ~a_j~-th weight on the left plate and the ~b_j~-th weight on the right plate.
Each weight must be placed on a plate, and one plate may only hold one weight. The number of tipped scales in your arrangement must be exactly ~M~. If there are multiple possible outputs satisfying these requirements, any of them will be accepted.
3 1 2 1 2 1 1
2 1 4 2 3 6 5
The first scale will tip to the right, and the second scale will tip to the left. The third scale remains balanced. It can be proven that this is the maximum possible number of tipped scales, so this is a valid arrangement of the weights.