BD-BDMO 2019 Problem 5

Prove that for all positive integers $n$ we can find a permutation of { $1,2,...,n$ } such that the average of two numbers doesn't appear in-between them.For example { $1,3,2,4$ }works,but { $1,4,2,3$ } doesn't because $2$ is between $1$ and $3$ .