EGMO 2016 Problem 1

Let $n$ be an odd positive integer, and let $x_{1}, x_{2}, \ldots, x_{n}$ be non-negative real numbers. Show that

$$\min _{i=1, \ldots, n}\left(x_{i}^{2}+x_{i+1}^{2}\right) \leq \max _{j=1, \ldots, n}\left(2 x_{j} x_{j+1}\right)$$

where $x_{n+1}=x_{1}$.