ISL 2013 A4

Let $n$ be a positive integer, and consider a sequence $a_{1}, a_{2}, \ldots, a_{n}$ of positive integers. Extend it periodically to an infinite sequence $a_{1}, a_{2}, \ldots$ by defining $a_{n+i}=a_{i}$ for all $i \geqslant 1$. If $$a_{1} \leqslant a_{2} \leqslant \cdots \leqslant a_{n} \leqslant a_{1}+n$$ and $$a_{a_{i}} \leqslant n+i-1 \text { for } i=1,2, \ldots, n$$ prove that $$a_{1}+\cdots+a_{n} \leqslant n^{2} .$$ (Germany)