Let $n \geqslant 2$. For an $n$-tuple of ordered real numbers
$$
\begin{array}{l}
A=\left(a_{1}, a_{2}, \cdots, a_{n}\right), \\
\text { let } \quad b_{k}=\max _{1 \leqslant i \leqslant k}, k=1,2, \cdots, n .
\end{array}
$$

The array $B=\left(b_{1}, b_{2}, \cdots, b_{n}\right)$ is called the "innovation array" of $A$; the number of distinct elements in $B$ is called the "innovation order" of $A$.

Consider all permutations of $1,2, \cdots, n$ (each permutation is regarded as an ordered array). For all permutations with an innovation order of 2, find the arithmetic mean of their first elements. (Supplied by Su Chun)
Solution 1: Let $A=\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ be a permutation of $1,2, \cdots, n$. Then the innovation order of $A$ is 2 if and only if its innovation array contains exactly two different elements $a_{1}$ and $n$. It is easy to see that $a_{1}$ can be any one of $1,2, \cdots, n-1$.

When $a_{1}=m$, the numbers $m+1, \cdots, n-1$ must appear after $n$ in $A$, and only some of the numbers $1, \cdots, m-1$ can appear between $m$ and $n$. Therefore, $n$ can only appear as $a_{2}, \cdots, a_{m+1}$.

When $a_{k+2}=n(0 \leqslant k \leqslant m-1)$, $a_{2}, \cdots, a_{k+1}$ can be any permutation of 6 elements chosen from $1, \cdots, m-1$, and $a_{k+3}, \cdots, a_{n}$ can be any permutation of the remaining $n-k-2$ elements.
Therefore, the number of permutations corresponding to $a_{k+2}=n$ is
$$
\mathrm{P}_{m-1}^{\mathrm{t}}(n-k-2)!=\frac{(m-1)!(n-k-2)!}{(m-k-1)!}.
$$

Let the total number of permutations with an innovation order of 2 be $x$, and the sum of the first elements of these permutations be $y$. From the above discussion, we have
$$
\begin{aligned}
x= & \sum_{m=1}^{n-1} \sum_{k=0}^{m-1} \frac{(m-1)!(n-k-1)!}{(m-k-1)!} \\
= & \sum_{m=1}^{n-1}(m-1)!(n-m-1)! \\
& \cdot \sum_{k=0}^{m-1} \frac{(n-k-2)!}{(m-k-1)!(n-m-1)!} \\
= & \sum_{m=1}^{n-1}(m-1)!(n-m-1)!\left(\mathrm{C}_{n-m-1}^{n-m-1}\right. \\
& \left.+\mathrm{C}_{n-m}^{n-m-1}+\cdots+\mathrm{C}_{n-2}^{n-m-1}\right) \\
= & \sum_{m=1}^{n-1}(m-1)!(n-m-1)!\mathrm{C}_{n-1}^{n-m} \\
= & (n-1)!\left(1+\frac{1}{2}+\cdots+\frac{1}{n-1}\right).
\end{aligned}
$$

And using the above calculation process, we have
$$
\begin{aligned}
y & =\sum_{m=1}^{n-1} \sum_{k=0}^{m-1} \frac{m!(n-k-1)!}{(m-k-1)!} \\
& =\sum_{m=1}^{n-1} m!(n-m-1)!C_{n-1}^{n-m} \\
& =(n-1)!\left(n-1+\frac{n-2}{2}+\frac{n-3}{3}+\cdots+\frac{1}{n-1}\right).
\end{aligned}
$$

Therefore, the arithmetic mean is
$$
\begin{aligned}
\frac{y}{x} & =\frac{n-1+\frac{n-2}{2}+\frac{n-3}{3}+\cdots+\frac{1}{n-1}}{1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n-1}} \\
& =n-\frac{n-1}{1+\frac{1}{2}+\cdots+\frac{1}{n-1}}.
\end{aligned}
$$

Solution 2: Let $a_{1}=m$, then $m$ can be any one of $1, \cdots, n-1$.

When $a_{1}=m$, we call $m+1, \cdots, n$ "large numbers" and $1, \cdots, m-1$ "small numbers". Among the "large numbers", $n$ should appear before the other numbers. Since there are $n-m$ "large numbers", the number of permutations with an innovation order of 2 corresponding to $a_{1}=m$ is
$$
\begin{aligned}
x_{m} & =\mathrm{C}_{n-1}^{n-m}(n-m-1)!(m-1)! \\
& =\frac{(n-1)!}{n-m}.
\end{aligned}
$$

Therefore, the arithmetic mean is
$$
\begin{array}{l}
\frac{\sum_{m=1}^{n-1} m x_{m}}{\sum_{m=1}^{1} x_{m}} \frac{(n-1)!\sum_{m=1}^{n-1} \frac{m}{n-m}}{(n-1)!\sum_{m=1}^{n-1} \frac{1}{n-m}} \\
=\frac{\sum_{m=1}^{n-1} \frac{n-m}{m}}{\sum_{m=1}^{n-1} \frac{1}{m}}=n \cdot \frac{n-1}{1+\frac{1}{2}+\cdots+\frac{1}{n-1}}.
\end{array}
$$