Question 75
A safe has $n$ compartments numbered $1$ to $n$. Initially each contains a card bearing its number. Vasya rearranges the cards so that compartment $i$ contains the number $a_i$. Petya may swap any two cards numbered $x,y$, paying $2|x-y|$ roubles. Prove that Petya can restore all cards to their original positions while paying at most $|a_1-1|+|a_2-2|+\cdots+|a_n-n|$ roubles. (I. Bogdanov, G. Ivanov)