Corrupted Sort

문제

Chloe wants to test her sorting skills. She has $nn$ cards with distinct integers from $11$ to $nn$ written on them. She asks her little brother Connor to first blindfold her and then arrange all cards in a row in some order. Positions of cards are numbered from $11$ to $nn$ from left to right.

Chloe doesn't know the order of the cards, but she wants to sort them, so that the leftmost card has number $11$ and the rightmost card has number $nn$ on it. Formally, for each $ii$ she wants the card on position $ii$ to have number $ii$ on it. To achieve the goal, Chloe can ask Connor to do one or more operations.

Each operation can be denoted by two integers $po{s}_{i}pos\_i$ and $po{s}_{j}pos\_j$ (). Connor looks at the cards on positions $po{s}_{i}pos\_i$ and $po{s}_{j}pos\_j$, and if the card on position $po{s}_{i}pos\_i$ has a bigger number than the card on position $po{s}_{j}pos\_j$, he swaps them. Otherwise, he does nothing. Connor also tells Chloe if he swapped the cards or not.

To make the game more interesting, after every $2n2n$ operations Connor chooses two distinct cards uniformly at random and swaps them without telling anything to Chloe.

If after some of Chloe's operations all cards become sorted, Chloe wins. Help Chloe to sort all cards using at most $1000010\backslash \; 000$ operations.

힌트

Initial card ordering in the example was $33$ $11$ $22$ (that is, the card on position $11$ had number $33$ on it, the card on position $22$ had number $11$, and the card on position $33$ had number $22$).