题目描述

考虑以下过程： $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$。 本题测评时开栈。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。