CGMO 2016 Problem 4

Let $n$ is a positive integers , $a_1,a_2,\cdots,a_n\in\{0,1,\cdots,n\}$ . For the integer $j$ $(1\le j\le n)$ ,define $b_j$ is the number of elements in the set $\{i|i\in\{1,\cdots,n\},a_i\ge j\}$ .For example ：When $n=3$ ,if $a_1=1,a_2=2,a_3=1$ ,then $b_1=3,b_2=1,b_3=0$ . $(1)$ Prove that $$\sum_{i=1}^{n}(i+a_i)^2\ge \sum_{i=1}^{n}(i+b_i)^2.$$ $(2)$ Prove that $$\sum_{i=1}^{n}(i+a_i)^k\ge \sum_{i=1}^{n}(i+b_i)^k,$$ for the integer $k\ge 3.$