Set $k=a_1$. First note that for $m<k$, \[ a_{a_m+1} + \dots + a_{a_{m+1}} \le \underbrace{a_{a_{m+1}} + \dots + a_{a_{m+1}}}_{a_{m+1}-a_m \text{ terms}} \le \left( a_{m+1}-a_m \right)(n+m). \]Then \begin{align*} a_1 + \dots + a_k &= a_1 + \dots + a_k \\ a_{a_1+1} + \dots + a_{a_2} &\le \left( a_2-a_1 \right)\left( n+1 \right) \\ a_{a_2+1} + \dots + a_{a_3} &\le (a_3-a_2)(n+2) \\ &\phantom\le\vdots \\ a_{a_{k-1}+1} + \dots + a_{a_k} &\le \left( a_k-a_{k-1} \right)(n+k-1) \\ a_{a_k+1} + \dots + a_n &\le (n-a_k)(n+k) \end{align*}Summing these yields the desired result. The notation is dense here, so an example that can help you follow along is $(3,5,8,11,11,12,12,12,13,13)$. The first line just says that the first $k = a_1$ terms are arbitrary. Each line after that represents a block of consecutive identical numbers, so for example the second line is bounding the block of $11$'s, the last line is bounding the block of $13$'s.

There is also a nice geometric interpretation. Draw a bar diagram, i.e. draw a bar with height $a_i$ above the interval $[i-1;i]$. This forms an 'upwards staircase' polygon $\mathcal{P}$, built on the interval $[0;n]$. Now reflect $\mathcal{P}$ on the line $x=y$ and translate it so its base would be on the segment $x=-n$, $0\le y\le n$. Call the resulting polygon $\mathcal{P}^*$. The condition is equivalent to $\mathcal{P}$ and $\mathcal{P}^*$ not intersecting each other. But then comparing with the area they occupy in the square $S=\{0\le x,y\le n\}$, we see that \[n^2\ge [\mathcal{P}\cap S]+[\mathcal{P}^*\cap S]=\sum_{i=1}^n \max\{a_i-n,0\}+\sum_{i=1}^n\min\{a_i,n\}=\sum_{i=1}^n a_i.\] EDIT. Or course it is - thanks manuel153.

Since $a_{a_1} \leq n$ and $a_1$ is the least term of the sequence, we deduce that $a_1 \leq n$, and hence $a_n \leq 2n$. Therefore, all our numbers are between $1$ and $2n$. If every $a_i$ is less or equal than $n$, what we are asked to prove is trivially true. So let's suppose that this does not happen, and let $a_{k+1}$ be the first term which is greater than $n$. We can write \[a_1 = r_1, \quad a_2 = r_2, \quad \ldots, \quad a_k = r_k, \quad a_{k+1} = n + r_{k+1}, \quad \ldots, \quad a_n = n + r_n\] where each $r_i$ is a number between $1$ and $n$. The condition $a_n \leq a_1 + n$ implies that $r_n \leq r_1$, so the order relations between the $r_i$ are as follows: \[r_{k+1} \leq \ldots \leq r_n \leq r_1 \leq r_2 \leq \ldots \leq r_k.\] Now, the sum of all the $a_i$ is $\left( \sum_{i=1}^n r_i \right) + n(n-k) = \left( \sum_{i=1}^n r_i \right) + n^2 - nk$, and this is less or equal than $n^2$ if and only if $\sum_{i=1}^n r_i \leq nk$. Notice that $r_1 \leq k$. Indeed, from the problem statement we know that $a_{r_1} = a_{a_1} \leq n$, which implies $r_1 \leq k$ because every term starting from the $(k+1)-$th term is greater than $n$. Once again, if every $r_i$ is less or equal than $k$, what we must prove is trivially true, so we'll suppose this is not the case. Let $r_{j+1}$ be the first term that is greater than $k$. (The previous remark shows that $r_{j+1} \in \{r_2, \ldots, r_k\}$.) For each $s$ between $1$ and $k-j$, we know that $r_{j+s} > k$, so we can write $r_{j+s} = k + t_s$ with $t_s > 0$. (Notice that $t_s$ is an increasing sequence, and all terms are less or equal than $n-k$.) From the condition in the problem statement, we have that $a_{a_{j+s}} \leq n + j + s - 1$, but also $a_{a_{j+s}} = a_{r_{j+s}} = a_{k+t_s} = n + r_{k+t_s}$. Putting these together we get $r_{k+t_s} \leq j+s-1$, and hence the same bound is also true for all the $r_{k+m}$ with $1 \leq m \leq t_s$. Now we make the following construction. Consider a board with $n$ columns and $1+(k-j)$ rows. In the first row we write the numbers $r_1, r_2, \ldots, r_n$ in that order. Then, for each $1 \leq s \leq k-j$, in the row $1+s$ we write the following numbers: $1$ in the squares corresponding to columns $k+1, k+2, \ldots, k+t_s$, and $-t_s$ in the square corresponding to column $j+s$. In this board, in every row (except the first one) the same of all numbers written is $0$. Hence, the sum of all numbers in the first row, which is what we want to prove that is less or equal than $nk$, is equal to the sum of all numbers written in the board. We will see now that in each column of the board the sum of the numbers written is less or equal than $k$, which will complete the proof. $(*)$ In the first $j$ columns we didn't write any number other than the corresponding $r_i$, which by definition of $j$ we know that is less or equal than $k$. $(*)$ In the columns of the form $j+s$, with $1 \leq s \leq k-j$, the only numbers that are written are $r_{j+s}$ in the first row and $-t_s$ in the row $1+s$. By definition of $t_s$, the sum of these two numbers is precisely $k$. $(*)$ In the columns of the form $k+x$, with $1 \leq x \leq n-k$, we have the number $r_{k+x}$ in the first row, and below that, as many ones as numbers $t_s$ there are such that $t_s \geq x$. If there is none, then there's nothing to prove since we already knew that $r_{k+x} \leq r_1 \leq k$. In other case, let $s'$ be the least number such that $t_{s'} \geq x$. Therefore, the number of ones in this column is $(k-j)-s'+1$. But $t_{s'} \geq x$ implies that $r_{k+x} \leq r_{k + t_{s'}} \leq j+s'-1$. Hence, the sum of the numbers in this column does not exceed $j+s'-1+(k-j)-s'+1 = k$. The proof is complete. $\blacksquare$

Wow, what an amazing beauty! Who proposed this problem? And how is it possible that such an exceptional problem has not been selected for the IMO paper? @randomusername: I think that your rotation by $ -90^\circ $ must be a reflection at the line with slope $+1$ through the origin.

@uglysolutions: I don' t understand the last part of the proof where you wrote that there were exactly $(k-j)+s'-1$ Ones in that column. Why exactly that amount of ones? And i think $s'$ equals to $1$, doesn't it?

@maths_lover5: In the square corresponding to row $1+s$ and column $k+x$, there is a $1$ iff $x \leq t_s$, and $0$ otherwise. So the total amount of ones in column $k+x$ (excluding the number $r_{k+x}$ from the first row, which could be $1$ as well) is equal to the cardinality of the set $A = \{ 1 \leq s \leq k-j : t_s \geq x \}$. Since $(t_s)$ is an increasing sequence, if $s'$ is the least possible number $s$ such that $t_s \geq x$, then $A = \{s', s'+1, \ldots, k-j\}$, which has $(k-j)-s'+1$ elements. This $s'$ depends on $x$, of course. Is it clear now?

EDIT: wow what a terrible solution...

reasonably different from the above solutions as far I can tell?

Let $k$ be the greatest integer for which $a_k\leq n$. It suffices to prove \[\sum_{i=1}^k a_i + \sum_{i=k+1}^n a_i \le n^2. \] We have $n\geq a_k$ by assumption. We also have $k-a_1$, because as the sequence is increasing, this is equivalent to $a_k\geq a_{a_1}$, and as $a_{a_1}\leq n$, if this were not true we would have a contradiction of $a_k$'s maximality under $n$. Thus, $(n-a_k)(k-a_1)\geq 0\implies ka_k+a_1n\leq kn+a_1a_k$. Now, let $m$ be the least integer for which $a_m>k$. I claim $km\geq \sum_{i=1}^{m-1}a_i + k$. Indeed, $k(m-1) \geq \sum_{i=1}^{m-1}a_i$ is clear because the sequence is nondecreasing, and $a_{m-1}$ is at most $k$ by assumption. Thus, $\sum_{i=1}^{m-1}a_i+k+ka_k+a_1n\leq kn+a_1a_k+km$, which implies \[\sum_{i=1}^k a_i+\left(\left(-\sum_{i=m}^ka_i\right)+(n+m-1)(-k)+a_k k+na_1-a_ka_1+n^2\right)\leq n^2\] Now, use the upper bounds in the second condition to produce \[\sum_{i=k+1}^n a_i\leq (a_m-k)(n+m-1)+(a_{m+1}-a_m)(n+(m+1)-1)+(a_{m+2}-a_{m+1})(n+(m+2)-1)\ldots+(a_k-a_{k-1})(n+k-1)+(n-a_k)(a_1+n)\] because the sequence is nondecreasing, and the terms of the sum give the number of terms that are between each upper bound. However, this telescopes to \[\sum_{i=k+1}^n a_i\leq (n+m-1)(-k)-a_m-a_{m+1}\ldots -a_{k-1}+(n+k-1)a_k+na_1-na_k-a_ka_1+n^2\] which implies \[\sum_{i=k+1}^n a_i\leq (n+m-1)(-k)-a_m-a_{m+1}\ldots -a_{k-1}+(n+k-1)a_k+na_1-na_k-a_ka_1+n^2\] and with some manipulation we get \[\sum_{i=k+1}^n a_i\leq \left(\left(-\sum_{i=m}^ka_i\right)+(n+m-1)(-k)+a_k k+na_1-a_ka_1+n^2\right)\] So from \[\sum_{i=1}^k a_i+\left(\left(-\sum_{i=m}^ka_i\right)+(n+m-1)(-k)+a_k k+na_1-a_ka_1+n^2\right)\leq n^2\] we get that $\sum_{i=1}^k a_i + \sum_{i=k+1}^n a_i \le n^2$ and we are done.

This solution looks too short so maybe i'm missing something crucial. Can someone please point it out, if so? lyukhson wrote: Let $n$ be a positive integer, and consider a sequence $a_1 , a_2 , \cdots , a_n $ of positive integers. Extend it periodically to an infinite sequence $a_1 , a_2 , \cdots $ by defining $a_{n+i} = a_i $ for all $i \ge 1$. If \[a_1 \le a_2 \le \cdots \le a_n \le a_1 +n \]and \[a_{a_i } \le n+i-1 \quad\text{for}\quad i=1,2,\cdots, n, \]prove that \[a_1 + \cdots +a_n \le n^2. \] Plot an "upward staircase" using the points $(i, a_i)$ for $1 \le i\le n$. Suppose $y=n$ splits the staircase into two regions: $\mathcal{R}$ above and $\mathcal{D}$ below. Call the region enclosed by $y=n$ and $\mathcal{D}$ as $\mathcal{B}$. It suffices to show $\text{Area}(\mathcal{B}) \ge \text{Area}(\mathcal{R})$ to prove $a_1+a_2+\dots+a_n \le n^2$ since the former is precisely the area of the whole staircase. Pick the maximal $r\le n$ for which $a_r \le n$. Note that $r \ge a_1$ since $a_{a_1} \le n$. Now partition $\mathcal{R}$ into disjoint rectangles made by $y=n$ and $(j, a_j), (j-1, a_j)$ for all $j>r$. The partition into disjoint rectangles made by $(a_j-n, a_{a_j}), (a_j-n, a_{a_{j}+1})$ and the $Y$-axis is a subset of $\mathcal{B}$ (note that the conditions ensure that this partition is valid). Each of these rectangles has area at least as much as the corresponding ones in $\mathcal{R}$, proving the bound.

v_Enhance wrote: Far easier than any of the other Algebra problems in my opinion; once you figure out where the equality cases are it's quite direct. First note that \[ a_{a_m+1} + \dots + a_{a_{m+1}} \le \underbrace{a_{a_{m+1}} + \dots + a_{a_{m+1}}}_{a_{m+1}-a_m \text{ terms}} \le \left( a_{m+1}-a_m \right)(n+m). \]Set $k=a_1$. Then \begin{align*} a_1 + \dots + a_k &= a_1 + \dots + a_k \\ a_{a_1+1} + \dots + a_{a_2} &\le \left( a_2-a_1 \right)\left( n+1 \right) \\ a_{a_2+1} + \dots + a_{a_3} &\le (a_3-a_2)(n+2) \\ &\phantom\le\vdots \\ a_{a_{k-1}+1} + \dots + a_{a_k} &\le \left( a_k-a_{k-1} \right)(n+k-1) \\ a_{a_k+1} + \dots + a_n &\le (n-a_k)(n+k) \end{align*}Summing these yields the desired result. But if $a_1 =a_2$ then $a_1 +1 >a_2$? Can anyone explain this please? And why the last term in the last row is $a_n $? Must not it be $a_{k+1} $? Please help me ...

Quote: But if $a_1 =a_2$ then $a_1 +1 >a_2$? Then both sides of the second row are zero, so no issue. The left-hand sum is empty. Quote: And why the last term in the last row is $a_n $? Must not it be $a_{k+1} $? I think it's fine as written. The point is you sum the rest of the terms that haven't been bounded yet. Here's an example that might be helpful for $n = 10$: \[ (3, 3, 8, 12, 12, 12, 12, 12, 13, 13). \]You can try following along the proof with that example. Some of the sums will be empty but this is fine.

v_Enhance wrote: Far easier than any of the other Algebra problems in my opinion; once you figure out where the equality cases are it's quite direct. First note that \[ a_{a_m+1} + \dots + a_{a_{m+1}} \le \underbrace{a_{a_{m+1}} + \dots + a_{a_{m+1}}}_{a_{m+1}-a_m \text{ terms}} \le \left( a_{m+1}-a_m \right)(n+m). \]Set $k=a_1$. Then \begin{align*} a_1 + \dots + a_k &= a_1 + \dots + a_k \\ a_{a_1+1} + \dots + a_{a_2} &\le \left( a_2-a_1 \right)\left( n+1 \right) \\ a_{a_2+1} + \dots + a_{a_3} &\le (a_3-a_2)(n+2) \\ &\phantom\le\vdots \\ a_{a_{k-1}+1} + \dots + a_{a_k} &\le \left( a_k-a_{k-1} \right)(n+k-1) \\ a_{a_k+1} + \dots + a_n &\le (n-a_k)(n+k) \end{align*}Summing these yields the desired result. Can somebody explain the first inequality? I think we need to prove $a_{a_m+t} \le a_{a_{m+1}}$ ,$(0 \le t \le a_{m+1}-a_m)$, which is sufficient if we have $a_m+t \le a_{m+1}$ as well as they are in the same period modulo $n$ (i.e. $\lceil \frac{a_m+t}{n} \rceil = \lceil \frac{a_{m+1}}{n} \rceil$ , but the latter seems not always true.

Let $a_1 \equiv n-t (mod \,n)$. By the second condition we have $a_1 \leq a_{n-t}=a_{a_1} \leq n$. So, $a_1= n-t$ and $a_n \leq 2n-t$ with $t \leq 0$. Find integers $l_i \geq 0$ such that \begin{align*} &a_1 = n-t+l_1\\ &a_2 = n-t+l_2 \\ & \dots \\ & a_{n-t}= n-t+l_{n-t} \end{align*}Note that, $a_{n-t+l_{n-t}}= a_{a_{n-t}} \leq 2n-t-1$, so $l_{n-t}$ numbers after $a_{n-t}$ are not bigger that $2n-t-1$, so upperbound of sum starting $a_{n-t+1}$ is limited by $$ \sum_{i=n-t+1}^{n}a_i \leq l_{n-t}(2n-t-1)+(2n-t)(t-l_{n-t})= (2n-t)t-l_{n-t}$$Repeating the process we get $$\sum_{i=1}^{n}a_i= \sum_{i=1}^{n-t}a_i + \sum_{i=n-t+1}^{n}a_i \leq (n-t)(n-t)+ \sum_{i=1}^{n-t}l_i + t(2n-t) - \sum_{i=1}^{n-t}l_i = n^2 $$

Imagine the grid $\{1, \dots, n\} \times \{1, \dots, n\}$. For each $k \le n$, mark the first $a_k$ cells of the sequence \[(k, 1), (k, 2), \dots, (k, n), (1, n-k+1), (2, n-k+1), \dots, (n, n-k+1).\]The conditions imply no cell is marked twice. Since there are $n^2$ cells, the desired statement follows.

Define \begin{align*} a_1 = &\dots = a_{b_1} \\ a_{b_1+1} = &\dots = a_{b_2}\\ & \vdots \\ a_{b_{k-1}+1}= &\dots = a_{a_1} \end{align*}Note that we have \begin{align*} a_{a_{b_2}}= &a_{a_{b_1+1}} \leq n+b_1\\ a_{a_{b_3}} = &a_{a_{b_2+1}} \leq n+b_2 \\ \vdots& \\ a_{a_{a_1}}= &a_{a_{b_{k-1}+1}} \leq n+b_{k-1} \end{align*}And $a_t \leq n+a_1 \ \ \forall a_{a_1} t \leq n $. Let $b_0=0$ and $b_k =a_1$. Now \begin{align*} \sum_{i=1} ^n a_i \leq \sum_{i=1} ^{k} (b_i - b_{i-1})(a_{b_i}) + \sum_{i=2}^k (a_{b_i} - a_{b_{i-1}})(n+b_{i-1}) + (n+a_1)(n-a_{b_k}) \\ = \sum_{i=1} ^{k} (b_i - b_{i-1})(a_{b_i}) + \sum_{i=2}^k (a_{b_i} - a_{b_{i-1}})(b_{i-1}) - na_{b_1} + n^2 +a_1 n - a_1 a_{b_k} \\ = a_{b_k} b_k +n^2 -a_1 a_{b_k} = n^2 \end{align*}We are done.

Suppose $a_1=m$. Then, we know that $a_m\le n$, so there are at most $n-m$ numbers in the (finite) sequence which are more than $n$. For now, assume that $a_i=m\,\,\forall i\le m$, and $a_i=n+m\,\,\forall i>m$. Of course, it is not necessary that all numbers with index $\le m$ are $m$, as they could be greater. So, we will modify them to their actual values starting from $a_m$ and going to $a_2$. If we add $k_m$ to $a_m$, we get that $a_{m+k_m}\le n+m-1$, so we know that the maximum value of the numbers between $a_{m+1}$ and $a_{m+k_m}$ is $n+m-1$, which is 1 less than before. So, by adding $k_m$ to $a_m$, we have to subtract $k_m$ from the maximum case. Similarly, if we add $k_{m-1}\le a_m$, we will also subtract exactly $k_{m-1}$ from the maximum case. So, once we are done adjusting the first $m$ numbers, are maximum case still has the same value, namely $m*m+(n+m)*(n-m)=n^2$, as desired.

This is a very cute problem. Let $k=a_1$. Note that $a_{a_1}\le n$, so $k=a_1=\min\{a_i\}\le n$ as well. We see that $a_k\le n$, so for each $1\le i\le k-1$, we have that $a_j\le n+i$ for $j\in[a_i+1,a_{i+1}]$, and we have $a_j\le n+a_1=n+k$ for $j\in[a_k+1,n]$. Thus, \[a_1+\cdots+a_n\le(a_1+\cdots+a_k)+\left[\sum_{i=1}^{k-1}(n+i)(a_{i+1}-a_i)\right]+(n+k)(n-a_k)=n^2.\]

Let $i=1$ in $a_{a_{i}} \leq n+i-1$ so this means $a_{a_{1}} \leq n $, meaning that if $a_1=k$ then $k \leq a_1,a_2,\dots,a_k \leq n $. while $a_{k+1},\dots , a_n \leq k+n $ adding all of this up we have : \[a_1+a_2+ \dots + a_n \leq k^2 + (n-k)(n+k)=n^2\]We want to show that $a_1+a_2+ \dots +a_n $ doesn't increase. We to increase $a_1,a_2,\dots a_k$ to it's original value. Firstly we have that the first $a_1$ terms are less than or equal to $n$ more than or equal to $k$, next we have that $(a_2-a_1)$ terms are less than or equal to $n+1$. The same goes for all remaining terms with indices less than $k+1$ while $a_i=n+k$ for $k+1 \leq i \leq n$ so we have that : \[a_1+a_2+\dots +a_k + (n+1)(a_2-a_1)+(n+2)(a_3-a_2)+\dots + (a_k-a_{k-1]})(n+k-1) + (n-a_k)(n+k)\]\[= k-(n+1)k + n^2+nk = n^2.\]Is the upper bound for $a_1+a_2+\dots+ a_n$ Hence we are done.

We will prove this using patching downwards induction. Define $f \colon N \rightarrow N$ as a function such that $f(n) = a_n$. First, we will prove this claim: $f(1) \leq n$. This is obviously true because $f(1) \leq f(f(1)) \leq n$. Base case: $f(k) \leq n$ for all $k$. This is trivial. Inductive step: Assume that the statement holds true for $m$, show it is true for $m - 1$. Assume $f(k) \leq n$ for $1 \leq k < m$. If $f(m) \leq n$, then we are done by the inductive hypothesis. Now consider the case $f(m) > n$. We claim $f(m) < n + m$. FTSoC assume $f(m) \geq n + m$. Then, because $f(1) \leq n$, we have $f(k) \leq f(1) + n = 2n$ for all $k$. Thus, it is impossible for $f(m) \geq 2n$, implying that $f(f(m)) \geq f(m) \geq n + m$, a contradiction. Now consider the possible values for $f(m)$. If $f(m) = n + m - 1$, then we must have $f(1) = f(2) = \dots = f(m - 1) = m-1$, and $f(m) = f(m + 1) = \dots = f(n) = n + m - 1$. We can add these together to see that we still have $f(1) + f(2) + \dots + f(n) \leq n^2$. We claim that no matter how we try to increase $f(1), f(2), \dots, f(m - 1)$, the corresponding decrease in $f(m), f(m + 1), \dots, f(n)$ keeps the total sum under $n^2$. We wish to increase $f(m - 1), f(m - 2), \dots, f((m - 1) - k + 1)$ from $m - 1$ to a value $a > m - 1$. Then, we must decrease $f(m), \dots, f(a)$ from $n + m - 1$ to $n + (m - k) - 1$, keeping the overall sum less than $n^2$, as desired. Thus, it is impossible to have $f(1) + f(2) + \dots + f(n)$ be greater than $n^2$.

This problem has very interesting equality cases. Let $S=a_1+a_2+\cdots+a_n$. Note that $a_{a_1}\leq n$, so at least one of the terms must be at most $n$. Since $a_1$ is the smallest term, we have $a_1\leq n$. If $a_1=1$, then $a_n\leq n+1$, which means $a_i\leq n+1$ for each $2\leq i\leq n$. So, $S\leq1+(n-1)(n+1)=n^2$. Now, we assume $a_1=k>1$. We know, $a_k=a_{a_1}\leq n$. Hence, for each $2\leq i\leq k$, we have $a_i\leq k$. Now, for each $2\leq i\leq k$, we also have $a_{a_i}\leq n+i-1$. So, for $a_{i-1}\leq m\leq a_i$, we have $a_m\leq n+i-1$. We bound the sum as follows: \[S\leq a_1+a_2+\cdots+a_k+(a_2-a_1)(n+1)+(a_3-a_2)(n+2)+\cdots+(a_k-a_{k-1})(n+k-1)+(n-a_k)(n+k)\]\[\Longrightarrow S\leq\sum_{i=1}^{k}a_i+\sum_{i=2}^{k}(n+i-1)(a_i-a_{i-1})+(n-a_k)(n+k)\]\[\Longrightarrow S\leq(n-a_k)(n+k)+\sum_{i=1}^{k}a_i+(n-1)\sum_{i=2}^{k}(a_i-a_{i-1})+\sum_{i=2}^{k}i(a_i-a_{i-1})\]Now, $\sum_{i=2}^{k}(a_i-a_{i-1})=a_k-a_1$ as it telescopes and the adjacent terms cancel out. Moreover, $\sum_{i=2}^{k}i(a_i-a_{i-1})=\sum_{i=2}^{k}ia_i-\sum_{i=1}^{k-1}ia_i-\sum_{i=1}^{k-1}a_i=ka_k-a_1-\sum_{i=1}^{k-1}a_i$ So, we have \[S\leq(n-a_k)(n+k)+\sum_{i=1}^{k}a_i+(n-1)(a_k-a_1)+ka_k-a_1-\sum_{i=1}^{k-1}a_i\]\[\Longrightarrow S\leq n^2-ka_k-na_k+nk+na_k+a_1-na_1-a_k+ka_k-a_1+a_k\]\[\Longrightarrow S\leq n^2,\]as desired. $\blacksquare$

We first notice that $a_i \leq n$ and $a_{a_i} \leq n$. We can partition the set $\{1,2,\ldots,n\}$ into \[\{a_x+1,\ldots,a_{x+1}\} \text{ for } 1 \leq x \leq a_1-1\] plus the sets $\{1,\ldots,a_1\}$ and $\{a_{a_1}+1,\ldots,n\}$. For each set beside the final two listed, we can multiply its largest element by its cardinality to get the upper bound for $a_1+a_2+\ldots+a_n$ to be \begin{align*} &(a_1+\ldots+a_{a_1}) + \left(\sum_{i=1}^{a_1-1} (a_{i+1}-a_i)(a_{a_{i+1}})\right) + (a_{a_{a_1}+1}+\ldots+a_n) \\ \ge ~&(a_1+\ldots+a_{a_1}) + \left(\sum_{i=1}^{a_1-1} (a_{i+1}-a_i)(n+i)\right) + (a_{a_{a_1}+1}+\ldots+a_n) \\ \ge ~&-na_1 + n(n+a_1) = n^2. \quad \blacksquare \end{align*}

Everyone else's but I explain the inequality in a different way. Consider $a_1.$ Note that if $a_1>n,$ then $a_n \leq n,$ so $a_1 \leq n.$ Note that if $a_1=n,$ then $a_n=n$ as well, which means everything is $n,$ satisfying the condition. Thus, let $a_1<n.$ Note that $a_i$ bounds the first $a_i$ terms to a maximum of $n+i-1,$ where $a_i<n.$ Consider the first $a_1$ terms of the sequence. If they are all $<n,$ then $a_{a_{a_1}} \leq n+a_1-1,$ and the problem statement gives that the maximum for all after is $n+a_1,$ so it can't go any larger than that, so the bounds steadily increase by $1$ each time we go from $a_{a_i}$ to $a_{a_{i+1}}.$ If some of the terms are $=n,$ then the bound is lower. Note that changing any terms after the $a_1$'th terms does nothing to the bounds because it gives boudns of $\leq n+a_1+1,$ which is useless, and the terms from $a_1$ to $a_{a_1}$ also don't effect eachother, except that they are all $\leq n.$ Let's start from the case with all $n$ terms being $=n.$ Define $x_i=n-a_i,$ and set terms from $a_1$ to $a_{a_1}.$ Firstly, we subtract $x_1$ from $n$ to get to $a_1.$ This causes the upper bound of the last $x_1$ terms to go up by one. Similarly, subtracting all $x_i$ from their respective $a_i$ causes the upperbound of the last $x_i$ to go up by one, and we can change all the terms to their upper bounds as changing terms after $a_{a_1}$ doesn't affect anything. Note that we we subtracted $\sum_{1}^{a_1} x_i$ from the first $a_1$ terms, and added $\sum_{1}^{a_1} x_i$ to the remaining terms, so the max sum is $n^2,$ as desired.$\blacksquare$

I've been solving shortlist problems for some time and this problem got me shocked because it's so easy for A4! $a_1 \leq a_{a_1} \leq n$, now call $a_1=n-a$, where $0 \leq a \leq n-1$ Consider all $a_i$ for $1 \leq i \leq n-a$. We know that $a_{n-a} \leq n$, so all of them are between $n-a$ and $n$. Denote the number of $n-a-1+i$ among them by $x_i$. Then $a_1+a_2+\ldots+a_{n-a} = x_1(n-a)+x_2(n-a+1)+\ldots+x_{a+1}n \leq n(n-a)-(x_1*a+\ldots+x_a*1)$. Also, by the given inequality $a_{n-a+i} \leq n+x_1+\ldots+x_i$ (Here we need to note, that when $x_1+\ldots+x_i < n$ it is second inequality from the problem statement, and when $x_1+\ldots+x_i=n$, we use $a_n \leq a_1+n$). Summarizing everything, we get $a_1+\ldots+a_n \leq n^2-(x_1*a+\ldots+x_a*1)+(x_1*a+\ldots+x_a*1)=n^2$, which is the desired.

Let $a_1 = k$. Simply note that $$\sum_{i=1}^n a_k \leq \sum_{i=1}^k a_i + \sum_{i=1}^{k-1} (a_{i+1}-a_i)(n+i) + (n+k)(n-a_k) = n^2,$$as desired.

Draw a bar graph with heights $a_i$. Color the region between the $a_i\le n$ and the line $y=n$ with red, as shown. Now: Consider some white square at the top of its column (below the red region) such that no white square is directly left of it, whose top-right corner is given by $(i,a_i)$. Reflection over $y=x$ takes this to $(a_i,i)$. This must be exactly one above the blue region (reflection of red region) now. Next, from $a_{a_i}\le n+i-1$ we must have $(a_i,a_{a_i})$ is at or below the $(a_i,n+i-1)$, which is a translation of $(a_i,i)$ by $n-1$. Thus defining the green region as the vertical translation of the blue region by $n$, the point $(a_i,a_{a_i})$ and its associated square must lie on or below the top wall (in its column) of the green region. Now combining the walls we have (using $a_i$ increasing) we get that, by our construction of the walls, each one is the rightmost in its row, so each one extends left until it reaches the previous wall (which may be at $y=n$, take $i=1$) and thus they draw out the boundary of the green region. However, we are still missing the wall in the last column. To resolve this, if the leftmost and topmost sides of the red region have total length $<n$, there must exist some segment on $y=n$ not touching red or green. Then if we call this segment red and take the square below it as our $i$, we get the desired bound for the right column. If otherwise, we use $a_n\le a_1+n$ and get the same bound. Thus all squares above $y=n$ are in the green region. Thus the total number of squares is at most the area of the square plus the area of the green region minus the area of the red region, which is just $n^2$ as desired. [asy][asy] size(8cm); fill((0,4)--(1,4)--(1,6)--(3,6)--(3,7)--(4,7)--(4,8)--(0,8)--cycle,palered); fill((4,0)--(8,0)--(8,4)--(7,4)--(7,3)--(6,3)--(6,1)--(4,1)--cycle,white+2*paleblue); fill((4,8)--(8,8)--(8,12)--(7,12)--(7,11)--(6,11)--(6,9)--(4,9)--cycle,palegreen); draw((4,9)--(6,9)); draw((6,11)--(7,11)); draw((7,12)--(8,12)); draw((4,8)--(4,9),dashed); draw((6,9)--(6,11),dashed); draw((7,11)--(7,12),dashed); draw((8,8)--(8,12),dashed); draw((-0.5,-0.5)--(8.5,8.5),dashed+linewidth(0.25)); draw((1.5,5.5)--(5.5,1.5),red+linewidth(0.4),EndArrow(5)); draw((5.5,1.5)--(5.5,8.5),blue+linewidth(0.4),EndArrow(5)); for(int i=0; i<=8; ++i) { draw((0,i)--(8,i)); draw((i,0)--(i,8)); } [/asy][/asy]

Since $a_{a_i} \le n+1-1=n$ and $a_{a_i} = a_{a_i \pmod{n}},$ we know $$a_1 \le n.$$Let $a_1=k,$ where $k$ is an integer at most $n.$ We know $$a_{k} \le n+1-1=n.$$ Let our `equality' case be when $$a_1=a_2=\dots=a_{k-1}=a_k=k,$$and $$a_{k+1}=a_{k+2}=\dots=a_n=n+k$$(note this sequence satisfies all the conditions, and the terms $a_{k+1}$ to $a_n$ are maximal). The sum of this sequence is $$k \cdot k + (n-k) (n+k) = n^2 \le n^2.$$ The idea is to use the values of $a_1$ to $a_k$ to create a bound on the total sum. Specifically, the values $a_1$ to $a_k$ (and thus the maximal sum) can be constructed from the equality case. Firstly, let all the terms in the sequence be the equality case (recall the the equality case is the maximal sequence given the starting state $a_1=a_2=\dots=a_k=k$). For any sequence from $a_1$ to $a_k$, we can construct it, from the equality, by a series of operations that add $1$ to the terms from $a_i$ to $a_k$ (note that the number of operations is at most $n-k$ because of $a_k \le n$). We preform these operations in order from largest range $a_i$ to $a_k$, to smallest (so $i$ is increasing). Let's preform one of these operations and see how the sequence is affected. Say we preform the $q$th (where $1 \le q \le n-k$) operation on $a_i$ to $a_k,$ we know (by the order we preformed the operations) that $a_i=a_{i+1}=\dots=a_k$ (this value is specifically $k+q-1$). If we add $1$ to all these elements, the total sum increases by $$k-i+1.$$However, we know $$a_{k+q}=a_{k+q-1 + 1} = a_{a_i} \le n+i-1.$$Since $k+1 \le k+q \le k+n-k=n$, we know beforehand in the equality case $a_{k+q}=n+k$ (also there are no operated bounds currently $a_{k+q}$ since $q$ is increasing). Therefore, after we have the bound $a_{k+q} \le n+i-1,$ the total sum must decrease by at least $$(n+k)-(n+i-1)=k-i-1.$$Thus, after any operation the total sum cannot increase. Since the maximal sum of any sequence can be constructed from the equality case and our operations, and the operations do not increase the total sum, the maximal sum of any sequence is at most $n^2$. \qed

Let us call a sequence $(a_i)$ optimal if it satisfies the conditions in the problem, and \[a_1 + a_2 + \dots + a_n = n^2.\] The optimal sequences of length 2 are $(1,3)$ and $(2,2)$. The optimal sequences of length 3 are $(1,4,4)$, $(2,2,5)$, $(2,3,4)$, and $(3,3,3)$. More generally, we claim that there are $2^{n - 1}$ optimal sequences of length $n$. In order to prove this, it will be helpful to have a visual representation of an optimal sequence. For example, below is the graph $\mathcal{G}$ of the optimal sequence \[7, \, 7, \, 11, \, 16, \ 18, \ 18, \, 18, \, 22, \, 22, \, 22, \, 22, \, 23, \, 23, \, 23, \, 23, \, 23, \, 24, \, 24, \, 27, \, 27.\] [asy][asy] unitsize(0.5 cm); defaultpen(fontsize(10)); int i, j; int[] seq; path toppath; seq[1] = 7; seq[2] = 7; seq[3] = 11; seq[4] = 16; seq[5] = 18; seq[6] = 18; seq[7] = 18; seq[8] = 22; seq[9] = 22; seq[10] = 22; seq[11] = 22; seq[12] = 23; seq[13] = 23; seq[14] = 23; seq[15] = 23; seq[16] = 23; seq[17] = 24; seq[18] = 24; seq[19] = 27; seq[20] = 27; toppath = (0,7)--(2,7)--(2,11)--(3,11)--(3,16)--(4,16)--(4,18)--(7,18)--(7,22)--(11,22)--(11,23)--(16,23)--(16,24)--(18,24)--(18,27)--(20,27); fill(toppath--(20,0)--(0,0)--cycle, paleblue); draw((0,0)--(0,seq[1]), gray(0.7)); for (i = 1; i <= 20; ++i) { draw((i,0)--(i,seq[i]), gray(0.7)); } for (j = 0; j <= 26; ++j) { i = 0; while (seq[i + 1] <= j) {++i;} draw((i,j)--(20,j), gray(0.7)); } for (i = 0; i <= 20; ++i) { label("$" + string(i) + "$", (i,0), S); } for (j = 0; j <= 27; ++j) { label("$" + string(j) + "$", (0,j), W); label("$" + string(j) + "$", (20,j), E); } draw(toppath); [/asy][/asy] Let $k = a_1 \le n$. By the solution in post #2, in an optimal sequence: the terms $a_{a_1 + 1}$, $a_{a_1 + 2}$, $\dots$, $a_{a_2}$ must be equal to $n + 1$ the terms $a_{a_2 + 1}$, $a_{a_2 + 2}$, $\dots$, $a_{a_3}$ must be equal to $n + 2$ $\dots$ the terms $a_{a_{k - 1} + 1}$, $a_{a_{k - 1} + 2}$, $\dots$, $a_{a_k}$ must be equal to $n + k - 1$ the terms $a_{a_k + 1}$, $a_{a_k + 2}$, $\dots$, $a_n$ must be equal to $n + k$ In terms of the graph $\mathcal{G}$, this means the following: Take the portion of the graph $\mathcal{G}$ that lies above the line $y = n$ (shown in green below), and reflect it over the line $y = x$. Then this shape must be congruent to the shape that lies above the graph $\mathcal{G}$ and below the line $y = n$ (shown in red). [asy][asy] unitsize(0.5 cm); defaultpen(fontsize(10)); int i, j; int[] seq; path toppath, firstpath, secondpath; seq[1] = 7; seq[2] = 7; seq[3] = 11; seq[4] = 16; seq[5] = 18; seq[6] = 18; seq[7] = 18; seq[8] = 22; seq[9] = 22; seq[10] = 22; seq[11] = 22; seq[12] = 23; seq[13] = 23; seq[14] = 23; seq[15] = 23; seq[16] = 23; seq[17] = 24; seq[18] = 24; seq[19] = 27; seq[20] = 27; toppath = (0,7)--(2,7)--(2,11)--(3,11)--(3,16)--(4,16)--(4,18)--(7,18)--(7,22)--(11,22)--(11,23)--(16,23)--(16,24)--(18,24)--(18,27)--(20,27); firstpath = (0,7)--(2,7)--(2,11)--(3,11)--(3,16)--(4,16)--(4,18)--(7,18)--(7,20); secondpath = (7,20)--(7,22)--(11,22)--(11,23)--(16,23)--(16,24)--(18,24)--(18,27)--(20,27); fill(firstpath--(20,20)--(20,0)--(0,0)--cycle, paleblue); fill(secondpath--(20,20)--(7,20)--cycle, palegreen); fill(firstpath--(0,20)--cycle, palered); draw((0,0)--(0,seq[1]), gray(0.7)); for (i = 0; i <= 6; ++i) { draw((i,0)--(i,20), gray(0.7)); } for (i = 7; i <= 20; ++i) { draw((i,0)--(i,seq[i]), gray(0.7)); } for (j = 0; j <= 19; ++j) { draw((0,j)--(20,j), gray(0.7)); } for (j = 21; j <= 26; ++j) { i = 0; while (seq[i + 1] <= j) {++i;} draw((i,j)--(20,j), gray(0.7)); } for (i = 0; i <= 20; ++i) { label("$" + string(i) + "$", (i,0), S); } for (j = 0; j <= 27; ++j) { label("$" + string(j) + "$", (0,j), W); label("$" + string(j) + "$", (20,j), E); } draw((0,20)--(20,20)); draw(toppath); [/asy][/asy] Consider the top border of the graph, which is a path that goes from $(0,k)$ to $(n,a_n)$, where every step is to the right or up. The path must pass through the point $(k,n)$ (since $a_k \le n$ and $a_{k + 1} > n$). Furthermore, the path must pass through the point $(1,k)$, since $a_1 = k$. So given $k = a_1$, every optimal sequence corresponds to a path that goes from $(1,k)$ to $(k,n)$, where every step is to the right or up. Note that the reminder of the path is uniquely determined (from the reflection observation above). So the number of optimal sequences with $a_1 = k$ is \[\binom{n - 1}{k - 1}.\] Summing over $1 \le k \le n$, we find that the number of optimal sequence of length $n$ is \[\binom{n - 1}{0} + \binom{n - 1}{1} + \dots + \binom{n - 1}{n - 1} = 2^{n - 1}.\] We can also prove this as follows: Given an optimal sequence $(a_i)$, define a sequence $(s_i)$, where $s_i$ is 0 if $a_i = a_{i + 1}$, and 1 if $a_i < a_{i + 1}$. Call the the sequence $(s_i)$ the signature of an optimal sequence. We list the signatures of all the optimal sequences of length 4. \[ \begin{array}{c|c} \text{Optimal Sequence} & \text{Signature} \\ \hline 1, 5, 5, 5 & 100 \\ 2, 2, 6, 6 & 010 \\ 2, 3, 5, 6 & 111 \\ 2, 4, 5, 5 & 110 \\ 3, 3, 3, 7 & 001 \\ 3, 3, 4, 6 & 011 \\ 3, 4, 4, 5 & 101 \\ 4, 4, 4, 4 & 000 \end{array} \] Note how all the signatures are different! More generally, there is a bijection between optimal sequences of length $n$ and binary sequences of length $n - 1$, via this signature mapping. (It then follows that there are $2^{n - 1}$ optimal sequences of length $n$.) To establish this bijection, we must show how to recover an optimal sequence from its signature. To understand this mapping better, consider the following diagram. [asy][asy] unitsize(0.5 cm); defaultpen(fontsize(10)); int i, j, s; int[] seq; path toppath; seq[1] = 7; seq[2] = 7; seq[3] = 11; seq[4] = 16; seq[5] = 18; seq[6] = 18; seq[7] = 18; seq[8] = 22; seq[9] = 22; seq[10] = 22; seq[11] = 22; seq[12] = 23; seq[13] = 23; seq[14] = 23; seq[15] = 23; seq[16] = 23; seq[17] = 24; seq[18] = 24; seq[19] = 27; seq[20] = 27; toppath = (0,7)--(2,7)--(2,11)--(3,11)--(3,16)--(4,16)--(4,18)--(7,18)--(7,22)--(11,22)--(11,23)--(16,23)--(16,24)--(18,24)--(18,27)--(20,27); draw((0,0)--(0,seq[1]), gray(0.7)); for (i = 0; i <= 6; ++i) { draw((i,0)--(i,20), gray(0.7)); } for (i = 7; i <= 20; ++i) { draw((i,0)--(i,seq[i]), gray(0.7)); } for (j = 0; j <= 19; ++j) { draw((0,j)--(20,j), gray(0.7)); } for (j = 21; j <= 26; ++j) { i = 0; while (seq[i + 1] <= j) {++i;} draw((i,j)--(20,j), gray(0.7)); } for (i = 0; i <= 20; ++i) { label("$" + string(i) + "$", (i,0), S); } for (j = 0; j <= 27; ++j) { label("$" + string(j) + "$", (0,j), W); label("$" + string(j) + "$", (20,j), E); } label("Signature:", (-2,-1.5)); for (i = 1; i <= 19; ++i) { s = 0; if (seq[i] < seq[i + 1]) {s = 1;} if (i <= 7) { label("$" + string(s) + "$", (i, -1.5), red); label("$" + string(s) + "$", (i, 6.5), red); } else { label("$" + string(s) + "$", (i, -1.5), blue); label("$" + string(s) + "$", (0.5, i), blue); } } draw(arc((2,7),0.4,270,360), red, Arrow(6)); draw(arc((3,11),0.4,270,360), red, Arrow(6)); draw(arc((4,16),0.4,270,360), red, Arrow(6)); draw(arc((7,18),0.4,270,360), red, Arrow(6)); draw(arc((2,11),0.4,180,90), blue, Arrow(6)); draw(arc((3,16),0.4,180,90), blue, Arrow(6)); draw(arc((4,18),0.4,180,90), blue, Arrow(6)); draw((0,20)--(20,20)); draw(toppath); [/asy][/asy] Consider the portion of the path from $(0,k)$ to $(k,n)$. On this portion of the path, a 1 in the signature tells us when to take a left turn. Also, we take the portion of the signature after $s_k$, and map it along the $y$-axis, starting at $y = k + 1$. A 1 in the signature along the $y$-axis tells us when to take a right turn. Thus, when we lay out the signature in this way, the path is uniquely determined. The only question remaining then is, how do we determine the starting point $(0,k)$ from the signature? In the example above, the number of left turns is equal to the number of right turns, plus one. We consider another example. [asy][asy] unitsize(0.5 cm); defaultpen(fontsize(10)); int i, j, s; int[] seq; path toppath; seq[1] = 12; seq[2] = 12; seq[3] = 12; seq[4] = 14; seq[5] = 14; seq[6] = 14; seq[7] = 14; seq[8] = 19; seq[9] = 19; seq[10] = 19; seq[11] = 19; seq[12] = 20; seq[13] = 23; seq[14] = 23; seq[15] = 27; seq[16] = 27; seq[17] = 27; seq[18] = 27; seq[19] = 27; seq[20] = 31; toppath = (0,12)--(3,12)--(3,14)--(7,14)--(7,19)--(11,19)--(11,20)--(12,20)--(12,23)--(14,23)--(14,27)--(19,27)--(19,31)--(20,31); draw((0,0)--(0,seq[1]), gray(0.7)); for (i = 0; i <= 12; ++i) { draw((i,0)--(i,20), gray(0.7)); } for (i = 13; i <= 20; ++i) { draw((i,0)--(i,seq[i]), gray(0.7)); } for (j = 0; j <= 19; ++j) { draw((0,j)--(20,j), gray(0.7)); } for (j = 21; j <= 30; ++j) { i = 0; while (seq[i + 1] <= j) {++i;} draw((i,j)--(20,j), gray(0.7)); } for (i = 0; i <= 20; ++i) { label("$" + string(i) + "$", (i,0), S); } for (j = 0; j <= 31; ++j) { label("$" + string(j) + "$", (0,j), W); label("$" + string(j) + "$", (20,j), E); } label("Signature:", (-2,-1.5)); for (i = 1; i <= 19; ++i) { s = 0; if (seq[i] < seq[i + 1]) {s = 1;} if (i <= 12) { label("$" + string(s) + "$", (i, -1.5), red); label("$" + string(s) + "$", (i, 11.5), red); } else { label("$" + string(s) + "$", (i, -1.5), blue); label("$" + string(s) + "$", (0.5, i), blue); } } draw(arc((3,12),0.4,270,360), red, Arrow(6)); draw(arc((7,14),0.4,270,360), red, Arrow(6)); draw(arc((11,19),0.4,270,360), red, Arrow(6)); draw(arc((12,20),0.4,270,360), red, Arrow(6)); draw(arc((3,14),0.4,180,90), blue, Arrow(6)); draw(arc((7,19),0.4,180,90), blue, Arrow(6)); draw((0,20)--(20,20)); draw(toppath); [/asy][/asy] In this example, the number of left turns is equal to the number of right turns, plus two. There is a right turn at $(11,20)$, but in general, right turns on to the line $y = n$ are not counted. Since left turns and right turns alternate, and the first and last turns are always left turns, the number of left turns always exceeds the number of right turns by either 1 or 2. Furthermore, the last turn always occurs at $x = k$. Thus, we can find the starting point $(0,k)$ of the path as follows: Let $t$ be the 1's in the signature. We can write $t = 2m$ or $t = 2m + 1$. Then $k$ is the index of the $(m + 1)$st 1 in the signature. (In addition, we note that $t$ is even if and only if the path reaches the line $y = n$ before the final turn, which means that the optimal sequence contains a term of $n$.) Let's try building the path from a signature with an example. Consider the signature \[1010111101010110110.\] There are 12 1's, and the index of the 7th 1 is 10, so $k = 10$. Hence, the starting point is $(0,10)$, which also tells us where to divide the signature. [asy][asy] unitsize(0.5 cm); defaultpen(fontsize(10)); int i, j, s; int[] seq; path toppath; seq[1] = 10; seq[2] = 12; seq[3] = 12; seq[4] = 14; seq[5] = 14; seq[6] = 15; seq[7] = 17; seq[8] = 18; seq[9] = 20; seq[10] = 20; seq[11] = 21; seq[12] = 21; seq[13] = 23; seq[14] = 23; seq[15] = 25; seq[16] = 26; seq[17] = 26; seq[18] = 27; seq[19] = 28; seq[20] = 28; toppath = (0,10)--(1,10)--(1,12)--(3,12)--(3,14)--(5,14)--(5,15)--(6,15)--(6,17)--(7,17)--(7,18)--(8,18)--(8,20)--(10,20)--(10,21)--(12,21)--(12,23)--(14,23)--(14,25)--(15,25)--(15,26)--(17,26)--(17,27)--(18,27)--(18,28)--(20,28); draw((0,0)--(0,seq[1]), gray(0.7)); for (i = 0; i <= 20; ++i) { draw((i,0)--(i,20), gray(0.7)); } for (j = 0; j <= 19; ++j) { draw((0,j)--(20,j), gray(0.7)); } for (i = 0; i <= 20; ++i) { label("$" + string(i) + "$", (i,0), S); } for (j = 0; j <= 20; ++j) { label("$" + string(j) + "$", (0,j), W); label("$" + string(j) + "$", (20,j), E); } label("Signature:", (-2,-1.5)); for (i = 1; i <= 19; ++i) { s = 0; if (seq[i] < seq[i + 1]) {s = 1;} if (i <= 10) { label("$" + string(s) + "$", (i, -1.5), red); label("$" + string(s) + "$", (i, 9.5), red); } else { label("$" + string(s) + "$", (i, -1.5), blue); label("$" + string(s) + "$", (0.5, i), blue); } } draw((0,20)--(20,20)); dot((0,10)); [/asy][/asy] We can then use the 1's to tell us where the path turns. [asy][asy] unitsize(0.5 cm); defaultpen(fontsize(10)); int i, j, s; int[] seq; path toppath; seq[1] = 10; seq[2] = 12; seq[3] = 12; seq[4] = 14; seq[5] = 14; seq[6] = 15; seq[7] = 17; seq[8] = 18; seq[9] = 20; seq[10] = 20; seq[11] = 21; seq[12] = 21; seq[13] = 23; seq[14] = 23; seq[15] = 25; seq[16] = 26; seq[17] = 26; seq[18] = 27; seq[19] = 28; seq[20] = 28; toppath = (0,10)--(1,10)--(1,12)--(3,12)--(3,14)--(5,14)--(5,15)--(6,15)--(6,17)--(7,17)--(7,18)--(8,18)--(8,20)--(10,20)--(10,21)--(12,21)--(12,23)--(14,23)--(14,25)--(15,25)--(15,26)--(17,26)--(17,27)--(18,27)--(18,28)--(20,28); draw((0,0)--(0,seq[1]), gray(0.7)); for (i = 0; i <= 7; ++i) { draw((i,0)--(i,20), gray(0.7)); } for (i = 8; i <= 20; ++i) { draw((i,0)--(i,seq[i]), gray(0.7)); } for (j = 0; j <= 19; ++j) { draw((0,j)--(20,j), gray(0.7)); } for (j = 21; j <= 27; ++j) { i = 0; while (seq[i + 1] <= j) {++i;} draw((i,j)--(20,j), gray(0.7)); } for (i = 0; i <= 20; ++i) { label("$" + string(i) + "$", (i,0), S); } for (j = 0; j <= 28; ++j) { label("$" + string(j) + "$", (0,j), W); label("$" + string(j) + "$", (20,j), E); } label("Signature:", (-2,-1.5)); for (i = 1; i <= 19; ++i) { s = 0; if (seq[i] < seq[i + 1]) {s = 1;} if (i <= 10) { label("$" + string(s) + "$", (i, -1.5), red); label("$" + string(s) + "$", (i, 9.5), red); } else { label("$" + string(s) + "$", (i, -1.5), blue); label("$" + string(s) + "$", (0.5, i), blue); } } draw(arc((1,10),0.4,270,360), red, Arrow(6)); draw(arc((3,12),0.4,270,360), red, Arrow(6)); draw(arc((5,14),0.4,270,360), red, Arrow(6)); draw(arc((6,15),0.4,270,360), red, Arrow(6)); draw(arc((7,17),0.4,270,360), red, Arrow(6)); draw(arc((8,18),0.4,270,360), red, Arrow(6)); draw(arc((10,20),0.4,270,360), red, Arrow(6)); draw(arc((3,14),0.4,180,90), blue, Arrow(6)); draw(arc((1,12),0.4,180,90), blue, Arrow(6)); draw(arc((3,14),0.4,180,90), blue, Arrow(6)); draw(arc((5,15),0.4,180,90), blue, Arrow(6)); draw(arc((6,17),0.4,180,90), blue, Arrow(6)); draw(arc((7,18),0.4,180,90), blue, Arrow(6)); draw((0,20)--(20,20)); draw(toppath); dot((0,10)); [/asy][/asy] Thus, the optimal sequence with signature 1010111101010110110 is \[10, \, 12, \, 12, \, 14, \, 14, \, 15, \, 17, \, 18, \, 20, \, 20, \, 21, \, 21, \, 23, \, 23, \, 25, \, 26, \, 26, \, 27, \, 28, \, 28.\]

Define $b_{n + i - 1}$ as the largest $j$ such that $a_j \le n + i - 1$. Then for $i \le b_n$, we know $a_i \le n$, so $a_i \le b_{n + i- 1}$, otherwise we would have $a_{a_i} > n + i - 1$. We also have $\sum_{b_n < i \le n} a_i = \sum_{n \le j \le 2n} j(b_{j + 1} - b_j) = 2nb_{2n} - (n + 1)b_n - \sum_{n < i < 2n} b_i = 2n^2 - (n + 1)b_n - \sum_{n < i < 2n} b_i$ (just counting the number of time each element appears). Thus we have $\sum a_i \le 2n^2 - (n + 1)b_n - \sum_{n < i < 2n} b_i + \sum_{n \le i < n + b_n} b_{i} = 2n^2 - nb_n - \sum_{n + b_n \le i \le 2n - 1} b_i $, so we want to prove $n^2 \ge nb_n + \sum_{n + b_n \le i \le 2n - 1} b_i $. In fact, we claim $b_{n + b_n} = n$, which finishes since $b$ is nondecreasing. To see this, assume for the sake of contradiction that $a_n > n + b_n $, this then forces $n \ge a_1 > b_n $, which gives $a_{a_i} > n$, contradiction.

Note that $a_1 \le n$, and therefore let $a_1 = n-k$. Note that $a_{n-k} \le n$. Now, out of $a_1, \dots, a_{n-k}$, let the first $t_1$ have value of $n-k$, the next $t_2$ have value of $n-k+1$, and so on till the last $t_{k+1}$ have value $n$. Observe that $a_{n-k +i} = a_{a_{t_1 + \dots + t_i + 1}} \le n + t_1 + \dots + t_i$. Therefore, $$a_1 + a_2 + \dots + a_n$$$$\le t_1(n-k) + t_2(n-k+1) + \dots + t_k(n-1)+ t_{k+1}(n) + kn + kt_1 + (k-1)t_2 + \dots + 2t_{k-1} + t_k$$$$= (t_1 + t_2 + \dots + t_{k+1})n + kn = n(n-k) + kn = n^2,$$proving the result. $\square$

Too combinatorics minded to find the algebra solution Too algebra minded to find the geometric solution Just right to find some goofy local one Let $a_1 \le a_2 \le \dots \le a_d \le n$ be the integers which are at most $n$ and let $n < a_{d+1} < \dots < a_n \le a_1 + n$ be the integers larger than $n$. Since $a_{a_1} \le n$, it follows that $d \ge a_1$. As such, note that for $j \ge d+1$, \[ a_{a_{j}-n} \le a_{a_1} \le a_d \le n \]so the bound always holds. We thus instead consider fixing $a_1, a_2, \dots, a_d$, and maximizing $a_{d+1}, a_{d+2}, \dots, a_n$ to be the maximum possible under the $a_{a_i}$ bound and $n+a_1 \le n+d$. The way to visualize this is that each $1 \le i \le d-1$ defines a roof on $[a_i, a_{i+1}]$ where the value of $a_j$ is at most $n+i-1$, and a root of at most $n+a_1 \le n+d$ on $[a_d+1, n]$. Then incrementing some $a_i$ where $a_i \ne a_{i+1}$ by $1$ decreases the height of the roof at $a_i$ by $1$, and we take $a_d$ to be maximal. We can thus repeatedly increment $a_d$ until it is $n$, and repeat this for $i = d-1, \dots, 1$ in that order ends with final case $a_1 = a_2 = \dots = a_d = n$, which implies that all $a_i$ are $n$ and the sum is at most $n^2$.

Let $a(1)=k$. Note $k\ge 1$, so \[a(k)\le n \implies a(1)\le a(2)\le \dots \le a(k)\le n.\]Since they're all $\le n$, \[a(a(1)+1)\le \dots \le a(a(2))\le n+1, \]\[a(a(2)+1)\le \dots \le a(a(3))\le n+2, \]\[\dots, \]\[a(a(k-1)+1)\le \dots \le a(a(k))\le n+k-1.\]Adding; \[a(k+1)+\dots+a(a(k)),\]\[\le (a(2)-a(1))(n+1)+\dots+(a(n+k)-a(n+k-1))(n+k-1),\]and adding on $a(1)+\dots+a(k)$ to both sides, \[\implies a(1)+\dots+a(a(k))\le (n+k)a(k)-n\cdot a(1).\]However, \[a(a(k)+1)+\dots+a(n)\le (n-a(k))(n+k),\]and adding; \[a(1)+\dots+a(n)\le ((n+k)a(k)-n\cdot a(1))+((n-a(k))(n+k))=n^2,\]as desired.

Solution : Call an $a_i$ pointer iff $a_i\leq n$ and $i\leq n$ in the sense it points to another element with index less than $n$ with an inequality. We get $a_{a_1}\leq n$, thus $a_1\leq n$ which implies that $a_j$, $1\leq j\leq a_1$ are pointers. We take in the following $a_0=0$ and that $a_0$ is a pointer. Now for every pointer $a_j$ up to $a_{a_1}$, we have $a_{a_j+1},a_{a_j+2},\cdot\cdot\cdot,a_{min(a_{j+1},n)}\leq n+j \Rightarrow a_{a_j+1}+a_{a_j+2}+\cdot\cdot\cdot+a_{min(a_{j+1},n)}\leq (min(a_{j+1},n)-a_{a_j})(n+j)$ Summing these yields the result.