IMO Shortlist

First, we claim that
$$\begin{equation*} a_{i} \leqslant n+i-1 \quad \text{ for } i=1,2, \ldots, n . \tag{3} \end{equation*}$$
Assume contrariwise that $i$ is the smallest counterexample. From $a_{n} \geqslant a_{n-1} \geqslant \cdots \geqslant a_{i} \geqslant n+i$ and $a_{a_{i}} \leqslant n+i-1$, taking into account the periodicity of our sequence, it follows that
$$\begin{equation*} a_{i} \text{ cannot be congruent to } i, i+1, \ldots, n-1 \text{, or } n(\bmod n) \text{. } \tag{4} \end{equation*}$$
Thus our assumption that $a_{i} \geqslant n+i$ implies the stronger statement that $a_{i} \geqslant 2 n+1$, which by $a_{1}+n \geqslant a_{n} \geqslant a_{i}$ gives $a_{1} \geqslant n+1$. The minimality of $i$ then yields $i=1$, and (4) becomes contradictory. This establishes our first claim.

In particular we now know that $a_{1} \leqslant n$. If $a_{n} \leqslant n$, then $a_{1} \leqslant \cdots \leqslant a_{n} \leqslant n$ and the desired inequality holds trivially. Otherwise, consider the number $t$ with $1 \leqslant t \leqslant n-1$ such that
$$\begin{equation*} a_{1} \leqslant a_{2} \leqslant \ldots \leqslant a_{t} \leqslant n<a_{t+1} \leqslant \ldots \leqslant a_{n} \tag{5} \end{equation*}$$
Since $1 \leqslant a_{1} \leqslant n$ and $a_{a_{1}} \leqslant n$ by (2), we have $a_{1} \leqslant t$ and hence $a_{n} \leqslant n+t$. Therefore if for each positive integer $i$ we let $b_{i}$ be the number of indices $j \in\{t+1, \ldots, n\}$ satisfying $a_{j} \geqslant n+i$, we have
$$b_{1} \geqslant b_{2} \geqslant \ldots \geqslant b_{t} \geqslant b_{t+1}=0$$
Next we claim that $a_{i}+b_{i} \leqslant n$ for $1 \leqslant i \leqslant t$. Indeed, by $n+i-1 \geqslant a_{a_{i}}$ and $a_{i} \leqslant n$, each $j$ with $a_{j} \geqslant n+i$ (thus $a_{j}>a_{a_{i}}$ ) belongs to $\left\{a_{i}+1, \ldots, n\right\}$, and for this reason $b_{i} \leqslant n-a_{i}$.

It follows from the definition of the $b_{i}$\,s and (5) that
$$a_{t+1}+\ldots+a_{n} \leqslant n(n-t)+b_{1}+\ldots+b_{t} .$$
Adding $a_{1}+\ldots+a_{t}$ to both sides and using that $a_{i}+b_{i} \leqslant n$ for $1 \leqslant i \leqslant t$, we get
$$a_{1}+a_{2}+\cdots+a_{n} \leqslant n(n-t)+n t=n^{2}$$
as we wished to prove.

In the first quadrant of an infinite grid, consider the increasing "staircase" obtained by shading in dark the bottom $a_{i}$ cells of the $i$th column for $1 \leqslant i \leqslant n$. We will prove that there are at most $n^{2}$ dark cells.

To do it, consider the $n \times n$ square $S$ in the first quadrant with a vertex at the origin. Also consider the $n \times n$ square directly to the left of $S$. Starting from its lower left corner, shade in light the leftmost $a_{j}$ cells of the $j$th row for $1 \leqslant j \leqslant n$. Equivalently, the light shading is obtained by reflecting the dark shading across the line $x=y$ and translating it $n$ units to the left. The figure below illustrates this construction for the sequence $6,6,6,7,7,7,8,12,12,14$.

We claim that there is no cell in $S$ which is both dark and light. Assume, contrariwise, that there is such a cell in column $i$. Consider the highest dark cell in column $i$ which is inside $S$. Since it is above a light cell and inside $S$, it must be light as well. There are two cases:

Case 1. $a_{i} \leqslant n$

If $a_{i} \leqslant n$ then this dark and light cell is $(i, a_{i})$, as highlighted in the figure. However, this is the $(n+i)$-th cell in row $a_{i}$, and we only shaded $a_{a_{i}}<n+i$ light cells in that row, a contradiction.

Case 2. $a_{i} \geqslant n+1$

If $a_{i} \geqslant n+1$, this dark and light cell is $(i, n)$. This is the $(n+i)$-th cell in row $n$ and we shaded $a_{n} \leqslant a_{1}+n$ light cells in this row, so we must have $i \leqslant a_{1}$. But $a_{1} \leqslant a_{a_{1}} \leqslant n$ by (1) and (2), so $i \leqslant a_{1}$ implies $a_{i} \leqslant a_{a_{1}} \leqslant n$, contradicting our assumption.

We conclude that there are no cells in $S$ which are both dark and light. It follows that the number of shaded cells in $S$ is at most $n^{2}$.

Finally, observe that if we had a light cell to the right of $S$, then by symmetry we would have a dark cell above $S$, and then the cell $(n, n)$ would be dark and light. It follows that the number of light cells in $S$ equals the number of dark cells outside of $S$, and therefore the number of shaded cells in $S$ equals $a_{1}+\cdots+a_{n}$. The desired result follows.

As in Solution 1, we first establish that $a_{i} \leqslant n+i-1$ for $1 \leqslant i \leqslant n$. Now define $c_{i}=\max \left(a_{i}, i\right)$ for $1 \leqslant i \leqslant n$ and extend the sequence $c_{1}, c_{2}, \ldots$ periodically modulo $n$. We claim that this sequence also satisfies the conditions of the problem.

For $1 \leqslant i<j \leqslant n$ we have $a_{i} \leqslant a_{j}$ and $i<j$, so $c_{i} \leqslant c_{j}$. Also $a_{n} \leqslant a_{1}+n$ and $n<1+n$ imply $c_{n} \leqslant c_{1}+n$. Finally, the definitions imply that $c_{c_{i}} \in\left\{a_{a_{i}}, a_{i}, a_{i}-n, i\right\}$ so $c_{c_{i}} \leqslant n+i-1$ by (2) and (3). This establishes (1) and (2) for $c_{1}, c_{2}, \ldots$.

Our new sequence has the additional property that
$$\begin{equation*} c_{i} \geqslant i \quad \text{ for } i=1,2, \ldots, n \tag{6} \end{equation*}$$
which allows us to construct the following visualization: Consider $n$ equally spaced points on a circle, sequentially labelled $1,2, \ldots, n(\bmod n)$, so point $k$ is also labelled $n+k$. We draw arrows from vertex $i$ to vertices $i+1, \ldots, c_{i}$ for $1 \leqslant i \leqslant n$, keeping in mind that $c_{i} \geqslant i$ by (6). Since $c_{i} \leqslant n+i-1$ by (3), no arrow will be drawn twice, and there is no arrow from a vertex to itself. The total number of arrows is
$$\text{ number of arrows }=\sum_{i=1}^{n}\left(c_{i}-i\right)=\sum_{i=1}^{n} c_{i}-\binom{n+1}{2}$$
Now we show that we never draw both arrows $i \rightarrow j$ and $j \rightarrow i$ for $1 \leqslant i<j \leqslant n$. Assume contrariwise. This means, respectively, that
$$i<j \leqslant c_{i} \quad \text{ and } \quad j<n+i \leqslant c_{j} .$$
We have $n+i \leqslant c_{j} \leqslant c_{1}+n$ by (1), so $i \leqslant c_{1}$. Since $c_{1} \leqslant n$ by (3), this implies that $c_{i} \leqslant c_{c_{1}} \leqslant n$ using (1) and (3). But then, using (1) again, $j \leqslant c_{i} \leqslant n$ implies $c_{j} \leqslant c_{c_{i}}$, which combined with $n+i \leqslant c_{j}$ gives us that $n+i \leqslant c_{c_{i}}$. This contradicts (2).

This means that the number of arrows is at most $\binom{n}{2}$, which implies that
$$\sum_{i=1}^{n} c_{i} \leqslant\binom{ n}{2}+\binom{n+1}{2}=n^{2} .$$
Recalling that $a_{i} \leqslant c_{i}$ for $1 \leqslant i \leqslant n$, the desired inequality follows.