对于 $30\%$ 的数据，$n\le10^3$。

对于 $100\%$ 的数据，$2\le n\le10^5$，$1\le a_i\le10^6$。