A respects week

Codeforces Global Round 9 was the main event of the Jun 29 - Jul 5 week (problems, results, top 5 on the left, analysis). The problemsetters warned us to read all problems before spending too much time on one of them, and yet my story is quite similar to Radewoosh's: I've spent 1.5 hours on problem F, and then solved problems G and H immediately after reading their problem statements, but lacked 5 minutes to finish the solution to H (it passed in practice). tourist, on the other hand, just didn't get stuck and got the first place with some margin. Well done!

Let me highlight a (relatively) easier problem this time, problem E: you are given an array a with at most 1000 elements. Then we write down all pairs of positions that form an inversion: pairs (u,v) such that u<v and a_u>a_v, getting a long list of all those pairs. Now we want to treat this list as a sorting program: for every pair in the list, we will swap the elements on the corresponding positions. Our goal is to make this program actually sort our array. We are allowed to put the elements of the list in arbitrary order (but we must have all pairs that form an inversion in the starting array exactly once). Can you see a way to achieve this?

Thanks for reading, and check back for more!