取数字

【题目描述】

考虑以下过程： $N$ 个互不相同的数围成一圈。 两个人从中轮流拿出一个数。 除了第一步以外，每步只能选那些旁边至少有一个空位的数。 有多个时，选较大的。 对于 $N$ 种第一步情形分别计算这种情况下第一个人拿到的数的总和。

【输入】

输入的第一行是整数 $N$。 第二行有 $N$ 个整数 $A_i$，按顺序描述了这一圈数。

【输出】

输出 $N$ 行，每行一个整数，描述了第一步选择对应的数时先手方最后的总分。

【输入样例】

3
1 2 3

【输出样例】

3
3
4

【提示】

【数据规模和约定】 对于20%的数据，$N≤5000$。 对于另外20%的数据，$A_i=i$。 对于另外30%的数据，数据随机生成。 对于100%的数据，$N≤300000，A_i≤10^9$。 本题测评时开栈。