Note $f(n) = \frac{n}{2\sqrt{n-1}}$ is strictly increasing for $n \geq 2.$ (keep this definition of $f(n)$ throughout) We can verify the result for $n=2$ with cases. Now assume result holds for $2 \leq n \leq k-1$ When $n=k$. Let $b_1=1.$ Define $b_{i+1}$ as the smallest integer larger than $b_i$ such that $a_{b_{i+1}} \geq a_{b_i}$ (defined only while $b_{i+1} \leq n$ exists) If $c$ is the largest integer for which $b_c$ is defined (by the definition above), let $b_{c+1} = n+1$ for convenience. First consider the case when $b_2<n+1.$ Then $b_{j+1}-b_j<n \ \forall j$ So $\sum_{i=b_j}^{b_{j+1}-1} max \{a_1,...,a_i \} \cdot min \{a_i,...,a_n \} \leq \sum_{i=b_j}^{b_{j+1}-1} a_{b_{j}} \cdot min \{a_i,...,a_{b_{j+1}-1} \} \leq f(b_{j+1}-b_j) \cdot \sum_{i=b_j}^{b_{j+1}-1} a_i^2 < f(n) \cdot \sum_{i=b_j}^{b_{j+1}-1} a_i^2$ Taking sum across all $1 \leq j \leq c$ we get the desired result. If $b_2 = n+1, a_1 = max \{a_1,...,a_n \}$ Now it is not hard to verify by a switching argument that $\sum_{i=1}^{n} max \{a_1,...,a_i \} \cdot min \{a_i,...,a_n \}$ is maximised (for $\{a_1,...,a_n \} = S$ where $S$ is a fixed multiset) when $a_1 \geq a_n \geq a_{n-1} \geq ... \geq a_2$ so just let the $a_i$ be ordered as such. Hence $\sum_{i=1}^{n} max \{a_1,...,a_i \} \cdot min \{a_i,...,a_n \} = a_1 \cdot (2a_2 + a_3 + ... + a_n) \leq \frac{n}{2\sqrt{n-1}} \cdot \sum_{i=1}^{n} a_i^2$ $\Leftrightarrow (a_1-\sqrt{n-1} \cdot \frac{2a_2+a_3+...+a_n}{n})^2 + \sum_{i=2}^{n} a_i^2 - (n-1) \cdot (\frac{2a_2+a_3+...+a_n}{n})^2 \geq 0$ Which is true by Cauchy Schwarz combined with the fact that $a_2$ is minimum.

ployup wrote: Note $f(n) = \frac{n}{2\sqrt{n-1}}$ is strictly increasing for $n \geq 2.$ (keep this definition of $f(n)$ throughout) We can verify the result for $n=2$ with cases. Now assume result holds for $2 \leq n \leq k-1$ When $n=k$. Let $b_1=1.$ Define $b_{i+1}$ as the smallest integer larger than $b_i$ such that $a_{b_{i+1}} \geq a_{b_i}$ (defined only while $b_{i+1} \leq n$ exists) If $c$ is the largest integer for which $b_c$ is defined (by the definition above), let $b_{c+1} = n+1$ for convenience. First consider the case when $b_2<n+1.$ Then $b_{j+1}-b_j<n \ \forall j$ So $\sum_{i=b_j}^{b_{j+1}-1} max \{a_1,...,a_i \} \cdot min \{a_i,...,a_n \} \leq \sum_{i=b_j}^{b_{j+1}-1} a_{b_{j}} \cdot min \{a_i,...,a_{b_{j+1}-1} \} \leq f(b_{j+1}-b_j) \cdot \sum_{i=b_j}^{b_{j+1}-1} a_i^2 < f(n) \cdot \sum_{i=b_j}^{b_{j+1}-1} a_i^2$ Taking sum across all $1 \leq j \leq c$ we get the desired result. If $b_2 = n+1, a_1 = max \{a_1,...,a_n \}$ Now it is not hard to verify by a switching argument that $\sum_{i=1}^{n} max \{a_1,...,a_i \} \cdot min \{a_i,...,a_n \}$ is maximised (for $\{a_1,...,a_n \} = S$ where $S$ is a fixed multiset) when $a_1 \geq a_n \geq a_{n-1} \geq ... \geq a_2$ so just let the $a_i$ be ordered as such. Hence $\sum_{i=1}^{n} max \{a_1,...,a_i \} \cdot min \{a_i,...,a_n \} = a_1 \cdot (2a_2 + a_3 + ... + a_n) \leq \frac{n}{2\sqrt{n-1}} \cdot \sum_{i=1}^{n} a_i^2$ $\Leftrightarrow (a_1-\sqrt{n-1} \cdot \frac{2a_2+a_3+...+a_n}{n})^2 + \sum_{i=2}^{n} a_i^2 - (n-1) \cdot (\frac{2a_2+a_3+...+a_n}{n})^2$ Which is true by Cauchy Schwarz combined with the fact that $a_2$ is minimum. Thank ployup.