2013 IMO Shortlist 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 \geq 1$. If $$a_{1} \leq a_{2} \leq \cdots \leq a_{n} \leq a_{1}+n$$ and $$a_{a_{i}} \leq n+i-1 \quad \text { for } i=1,2, \ldots, n$$ prove that $$a_{1}+\cdots+a_{n} \leq n^{2} .$$ (Germany)

令 $n$ 为正整数，并考虑正整数序列 $a_{1}, a_{2}, \ldots, a_{n}$。通过为所有 $i \geq 1$ 定义 $a_{n+i}=a_{i}$，将其定期扩展为无限序列 $a_{1}, a_{2}, \ldots$。如果 $$a_{1} \leq a_{2} \leq \cdots \leq a_{n} \leq a_{1}+n$$ 和 $$a_{a_{i}} \leq n+i-1 \quad \text { for } i=1,2, \ldots, n$$ 证明 $$a_{1}+\cdots+a_{n} \leq n^{2} 。$$(德国)