(USAMO 2010 P2)

There are $n$ students standing in a circle, one behind the other, with heights $h_{1}<h_{2}<\ldots<h_{n}$. At any moment, if a student of height $h_{k}$ is directly behind a student of height less than or equal to $h_{k-2}$, they can decide to swap places. Determine the maximum number of swaps that can occur among all initial configurations and choices of swaps.
Let's start by studying the configuration where the students are in the order $1, 2, \ldots, n$ on the circle. In this case, student $n$ can swap with the student in front of him $n-2$ times, until he is just behind student $n-1$. Then, students $n-1$ and $n$, each in turn, swap with the student in front of them, until they reach the end in the order $n, n-1, n-2$, each making $n-3$ swaps. Next, students $n-2, n-1$, and $n$ each, in turn, swap with the student in front of them, $n-3$ times. They continue this process until the $n-2$ students $3, 4, \ldots, n$ each, in turn, swap with student 1. In the end, the students are in the reverse order of the initial order, i.e., $n, n-1, \ldots, 1$, and no student can make any more swaps. In total, the number of swaps made is

$$
\begin{gathered}
1 \times (n-2) + 2 \times (n-3) + \ldots + (n-2) \times 1 = \frac{(n-2)(n-1)}{2}(n-1) - \frac{(n-2)(n-1)(2n-3)}{6} \\
= \frac{n(n-1)(n-2)}{3} = \binom{n}{3}
\end{gathered}
$$

Now, let's show that it is not possible to do better than $\binom{n}{3}$ swaps. For this, we show that for any $m$, student $m$ can swap with smaller students at most $\binom{m-1}{2}$ times. We prove this by induction. If $m \leq 2$, it is true. Suppose the result is true for $m$, consider student $m+1$. Note that this student can never swap with student $m$, and let $d$ be the number of students smaller than $m$ in front of $m+1$ and behind $m$ on the circle. Then, at the beginning, $d$ is at most $m-1$, it decreases by 1 each time $m+1$ swaps with a smaller student, and increases by 1 if $m$ swaps with a smaller student. But $m$ can only swap $\binom{m-1}{2}$ times with smaller students, so $m+1$ can only swap

$$
m-1 + \binom{m-1}{2} = \binom{m}{2}
$$

times with smaller students. Therefore, the total number of swaps cannot exceed

$$
\binom{n-1}{2} + \binom{n-2}{2} + \ldots + \binom{2}{2} = \binom{n}{3}
$$