TUYMAADA 2016 Problem 1

The sequence $(a_n)$ is defined by $a_1=0$ , $$a_{n+1}={a_1+a_2+\ldots+a_n\over n}+1.$$ Prove that $a_{2016}>{1\over 2}+a_{1000}$ .