TUYMAADA 2014 S5

There is an even number of cards on a table; a positive integer is written on each card. Let $a_k$ be the number of cards having $k$ written on them. It is known that $$a_n-a_{n-1}+a_{n-2}- \cdots \ge 0$$ for each positive integer $n$ . Prove that the cards can be partitioned into pairs so that the numbers in each pair differ by $1$ .

(A. Golovanov)