题目描述

桌子上有从 $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

输入

5
3
5
1
7
6

输出

7
12
10

样例2

输入

20
623239331
125587558
908010226
866053126
389255266
859393857
596640443
60521559
11284043
930138174
936349374
810093502
521142682
918991183
743833745
739411636
276010057
577098544
551216812
816623724

输出

936349374
1855340557
2763350783
3622744640
4439368364
5243250666
5982662302
6605901633
7183000177
7309502029

说明/提示

数据范围

所有数据满足以下限制：

$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$。

源码