The sequence $x_1, x_2, ..., x_n$ of positive integers contains at least $\frac {2n}{3}+1$ distinct numbers and each of them appears at most three times. How to prove that there is a permutation $y_1, y_2, ..., y_n$ of $x_1, x_2, ..., x_n$ such that the $n$ sums $y_i+y_{i+1}$ are all distinct, where $1\le i\le n$ and $y_{n+1}=y_1$?

This problem was proposed on a math contest and as far as I'm concerned nobody managed to solve it, moreover the official solution was flawed. Or maybe this is false? In case it's true, can it be generalized?

Any reference or help would be appreciated.