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