BALTIC-WAY 2007 Problem 4

Let $a_1,a_2,\ldots ,a_n$ be positive real numbers, and let $S=a_1+a_2 +\ldots +a_n$ . Prove that $$(2S+n)(2S+a_1a_2+a_2a_3+\ldots +a_na_1)\ge 9(\sqrt{a_1a_2}+\sqrt{a_2a_3}+\ldots +\sqrt{a_na_1})^2$$