OMM 2005 Problem 4

A list of numbers $a_1,a_2,\ldots,a_m$ contains an arithmetic trio $a_i, a_j, a_k$ if $i < j < k$ and $2a_j = a_i + a_k$ . Let $n$ be a positive integer. Show that the numbers $1, 2, 3, \ldots, n$ can be reordered in a list that does not contain arithmetic trios.