Suppose that $a_k^2+S_{n-k}\ge 2S_n-\frac{n(n+1)}{2}$ is satisfied for all $1\leq k\leq n$. $(n-a_k)(k-a_k)\le 0\implies a_k^2 +(n-k)a_k\le 2na_k -nk$ $\implies \sum_{k=1}^n (a_k^2 +(n-k)a_k)\le \sum_{k=1}^n (2na_k -nk)\implies \sum_{k=1}^n (a_k^2 +S_{n-k})\le 2nS_n -n\cdot\frac{n(n+1)}{2} $ $\therefore \sum_{k=1}^n (a_k^2+S_{n-k})\le \sum_{k=1}^n (2S_n-\frac{n(n+1)}{2} )\implies a_k^2+S_{n-k}=2S_n-\frac{n(n+1)}{2}$ for all $1\leq k\leq n$. By $(n-a_k)(k-a_k)\le 0$, we get $a_k=k$ or $n$ for all $1\leq k\leq n$ too. $a_1^2+S_{n-1}=2S_n-\frac{n(n+1)}{2} =a_2^2+S_{n-2}\implies a_2^2 -a_1^2 =S_{n-1}-S_{n-2}=a_{n-1}$ $n\neq 3,4$: contradiction. $n=3,4$: $a_3^2 -a_2^2 =S_{n-2}-S_{n-3}=a_{n-2}$. contradiction. $\therefore$ There exists such $1\leq k\leq n$ that satisfies $a_k^2+S_{n-k}<2S_n-\frac{n(n+1)}{2}$. Q.E.D.