3. Let $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ be a permutation of the numbers $1,2, \ldots, n$, where $n \geq 2$. Determine the maximum possible value of the expression

$$
\sum_{k=1}^{n-1}\left|a_{k+1}-a_{k}\right|
$$

(Romania)
3. We will consider the sum $S=\sum_{i=1}^{n}\left|a_{i}-a_{i+1}\right|$, where $a_{n+1}=a_{1}$. This sum can be written in the form

$$
S=\sum_{i=1}^{n} \epsilon_{i}\left(a_{i}-a_{i+1}\right)=\sum_{i=1}^{n} c_{i} a_{i} \quad \text { for some } \quad \epsilon_{i} \in\{-1,1\} \quad \text { and } \quad c_{i}=\epsilon_{i}-\epsilon_{i-1},
$$

where $\epsilon_{0}=\epsilon_{n}$. For each $i$, $c_{i} \in\{-2,0,2\}$. Consider the sets $A=\left\{i \mid c_{i}=2\right\}$ and $B=\left\{i \mid c_{i}=-2\right\}$. Since $c_{1}+c_{2}+\cdots+c_{n}=0$, we have $|A|=|B|=k$ for some $k \leqslant \frac{n}{2}$. Now we have

$$
S=2 \sum_{i \in A} x_{i}-2 \sum_{i \in B} x_{i} \leqslant 2[n+(n-1)+\cdots+(n-k+1)]-2[1+2+\cdots+k]=2 k(n-k)
$$

The expression $2 k(n-k)$ is maximized for $k=\left[\frac{n}{2}\right]$ and is then equal to $\left[\frac{n^{2}}{2}\right]$. Finally, since $\left|a_{n}-a_{1}\right| \geqslant 1$, we have

$$
S \leqslant\left[\frac{n^{2}}{2}\right]-1
$$

Equality is achieved, for example, for the permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)=(m+1,1, m+2,2, m+3,3, \ldots, m)$, where $m=n-\left[\frac{n}{2}\right]$.

Second solution. The sum $S=\sum_{i=1}^{n}\left|a_{i}-a_{i+1}\right|$ represents the length $\ell$ of the closed broken line $A_{1} A_{2} \ldots A_{n} A_{1}$, where $A_{i}$ is a point on the real line with coordinate $a_{i}$.

For each $k=1, \ldots, n-1$, consider the unit segment $[k, k+1]$. Each of the $n$ segments $A_{i} A_{i+1}$ that covers it has one endpoint in the interval $[1, k]$, and the other in the interval $[k+1, \ldots, n]$. It follows that this segment is covered by at most $2 \min \{k, n-k\}$ segments $A_{i} A_{i+1}(1 \leqslant i \leqslant n)$. In total, the observed broken line covers at most $2 \sum_{k=1}^{n-1} \min \{k, n-k\}=\left[\frac{n^{2}}{2}\right]$ unit segments, hence $\ell \leqslant\left[\frac{n^{2}}{2}\right]$.

Finally, due to $\left|a_{n}-a_{1}\right| \geqslant 1$, the desired sum is not greater than $\left[\frac{n^{2}}{2}\right]-1$.