U167463 「WWR2」Sweet Game

Sept 有 $n$ 颗糖，吃第 $i$ 颗糖会得到 $a_i$ 的甜度，现在他想请 Cindy 吃掉所有的糖。 但是，如果要吃第 $k$ 颗糖，必须在吃它之前或之后吃完第 $k+1\sim n$ 颗糖。 换句话说，当 $k

无

无

#### 样例 1 说明 对于这个样例，$\texttt{2 3 4 1}$ 是最佳的顺序。按照此顺序，Cindy 得到的甜度依次是 $1,0,3,7$，总甜度是 $1+0+3+7=11$。 该顺序也符合 Sept 的要求。 #### 样例 2 说明 对于这个样例，$\texttt{2 3 1}$ 是最佳的顺序。 #### 数据规模与约定 $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c}\hline\hline \textbf{Subtask} & n & \textbf{分值} \\\hline \textsf{1} & \le 100 & 20 \\\hline \textsf{2} & \le 10^3 & 40 \\\hline \textsf{3} & \text{无特殊限制} & 40 \\\hline\hline \end{array} $$ 对于 $100\%$ 的数据，有 $1\le n\le 2\times 10^5$，$1\le a_i\le 100$，$-100\le \Delta d_i\le 100$。