AT_joisc2018_j 飴 (Candies)

[problemUrl]: https://atcoder.jp/contests/joisc2018/tasks/joisc2018_j 桌子上有从 $1$ 到 $n$ 的糖排列着，每一块糖都有一个美味值 $a_{i}$，不能同时吃相邻的两颗糖，你需要求出当吃 $1,2,3……\left \lceil \frac{n}{2} \right \rceil $ 颗糖时能够得到的美味值的和的最大值。

第一行为一个正整数 $n$。 接下来 $n$ 行，每行一个数，代表第 $i$ 颗糖的美味值 $a_{i}$。

一共有 $\left \lceil \frac{n}{2} \right \rceil $ 行，分别表示当吃 $1,2,3……\left \lceil \frac{n}{2} \right \rceil $ 颗糖时美味值的和的最大值。

所有数据满足以下限制： $1\le n\le 2\times 10^{5}$ $1\le a_{i}\le 10^{9}$ 其中 $8\%$ 的数据满足：$1\le n\le 2000$ 其余测试点无特殊限制。 **【样例解释 \#1】** 只吃一颗糖选第四个美味值为 $7$ 为最大值。 吃两颗糖选第二个和第四个最优，美味值为 $5+7=12$。 吃三颗糖由于不能吃相邻的两颗糖所以只能选第一个，第三个和第五个，美味值为 $3+1+6=10$。