BALTIC-WAY 2007 Problem 6

Freddy writes down numbers $1, 2,\ldots ,n$ in some order. Then he makes a list of all pairs $(i, j)$ such that $1\le i<j\le n$ and the $i$ -th number is bigger than the $j$ -th number in his permutation. After that, Freddy repeats the following action while possible: choose a pair $(i, j)$ from the current list, interchange the $i$ -th and the $j$ -th number in the current permutation, and delete $(i, j)$ from the list. Prove that Freddy can choose pairs in such an order that, after the process finishes, the numbers in the permutation are in ascending order.