3. Let $n$ be a given even number, and $a_{1}, a_{2}, \cdots, a_{n}$ be $n$ non-negative real numbers whose sum is 1. Find the maximum possible value of
$$
S=\sum_{1 \leqslant i<j \leqslant n} \min \left\{(j-i)^{2},(n-j+i)^{2}\right\} a_{i} a_{j}
$$

(Fu Yunhao)
3. Solution 1 Let $n=2 k$.

When $a_{1}=a_{k+1}=\frac{1}{2}$, and the rest of $a_{i}$ are 0, $S=\frac{n^{2}}{16}$.
Let $\varepsilon=\cos \frac{2 \pi}{n}+\mathrm{i} \sin \frac{2 \pi}{n}$,
$$
z=a_{1} \varepsilon+a_{2} \varepsilon^{2}+\cdots+a_{n} \varepsilon^{n}.
$$

Then $0 \leqslant|z|^{2}=z \bar{z}$
$$
\begin{array}{l}
=\left(\sum_{j=1}^{n} a_{j} \varepsilon^{j}\right)\left(\sum_{j=1}^{n} a_{j} \varepsilon^{-j}\right) \\
=\sum_{i=1}^{n} a_{i}^{2}+\sum_{1 \leqslant i\sin \frac{2 \pi}{k}-\sin \frac{\pi}{k}>\cdots
$$
>\sin \frac{k \pi}{k}-\sin \frac{(k-1) \pi}{k},
$$

It is easy to see that equation (1) holds.
In summary, the maximum possible value is $\frac{n^{2}}{16}$.
Solution 2 Let $n=2 k$.
On one hand, when $a_{1}=a_{k+1}=\frac{1}{2}$, and the rest of $a_{i}$ are 0, $S=\frac{n^{2}}{16}$.
On the other hand, for any $1 \leqslant m \leqslant k$, we have
$$
\begin{array}{l}
\left(\sum_{i=m}^{m+k-1} a_{i}\right)\left(\sum_{j=m+k}^{m+2 k-1} a_{j}\right) \\
\leqslant\left(\frac{1}{2} \sum_{i=1}^{2 k} a_{i}\right)^{2}=\frac{1}{4},
\end{array}
$$

where the indices are taken modulo $2 k$.
$$
\begin{aligned}
& \text { Hence } \frac{n^{2}}{16}=\frac{k^{2}}{4} \\
\geqslant & k \sum_{m=1}^{k}\left(\left(\sum_{i=m}^{m+k-1} a_{i}\right)\left(\sum_{j=m+k}^{m+2 k-1} a_{j}\right)\right) \\
= & k \sum_{1 \leqslant i<j \leqslant n} \min \{j-i, n-j+i\} a_{i} a_{j} \\
\geqslant & \sum_{1 \leqslant i<j \leqslant n} \min \left\{(j-i)^{2},(n-j+i)^{2}\right\} a_{i} a_{j} .
\end{aligned}
$$

In summary, the maximum possible value is $\frac{n^{2}}{16}$.