JOI 君和 IOI 酱是双胞胎兄妹。JOI 君最近迷上了做点心，今天他烤好了一个蛋糕准备吃，但 IOI 酱闻到香味赶来了，于是两人决定分掉这个蛋糕。

蛋糕是圆形的。从某一点开始放射状地切开，将蛋糕分成了 $N$ 个部分，并按逆时针方向将这些部分编号为 $1$ 到 $N$。也就是说，对于 $1 \le i \le N$，第 $i$ 个部分与第 $i-1$ 个部分和第 $i+1$ 个部分相邻（其中第 $0$ 个部分视为第 $N$ 个部分，第 $N+1$ 个部分视为第 $1$ 个部分）。第 $i$ 个部分的大小为 $A_i$，由于切得非常不均匀，所有的 $A_i$ 互不相同。

图 1: 蛋糕示例 ($N = 5, A_1 = 2, A_2 = 8, A_3 = 1, A_4 = 10, A_5 = 9$)

两人决定按以下方式分这 $N$ 个部分：

• 首先，JOI 君从 $N$ 个部分中选择并拿走 $1$ 个。
• 之后，从 IOI 酱开始，IOI 酱和 JOI 君轮流从剩下的部分中各拿走 $1$ 个。但是（由于两人都不擅长在不弄碎蛋糕的情况下拿取），他们只能拿走那些“与其相邻的两个部分中至少有一个已经被拿走”的部分。如果存在多个可选的部分，则选择其中最大的一个拿走。

JOI 君想知道，对于每一个部分，如果他最开始选择拿走该部分，那么他最终拿到的所有部分的大小之和是多少。

题目描述

给定蛋糕部分的数量 $N$ 以及每个部分的大小信息，请编写一个程序，计算对于每一个部分，如果 JOI 君最开始选择拿走该部分，他最终拿到的部分大小之和。

输入格式

从标准输入读取以下内容：

• 第 $1$ 行包含一个整数 $N$，表示蛋糕被分成了 $N$ 个部分。
• 接下来的 $N$ 行中的第 $i$ 行 ($1 \le i \le N$) 包含一个整数 $A_i$，表示第 $i$ 个部分的大小。

输出格式

向标准输出输出 $N$ 行。第 $i$ 行 ($1 \le i \le N$) 输出一个整数，表示如果最开始拿走第 $i$ 个部分，JOI 君最终拿到的部分大小之和。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 300\,000$
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$)

子任务

子任务 1 [10 分]

• 满足 $N \le 5\,000$。

子任务 2 [90 分]

• 没有额外限制。

样例

输入 1

5
2
8
1
10
9

输出 1

13
18
12
13
12

说明

该示例对应题目中的图示。 例如，假设最开始拿走了第 $1$ 个部分。此时：

• 在剩下的部分中，“相邻部分中至少有一个已被拿走”的部分是第 $2$ 个和第 $5$ 个。由于第 $5$ 个部分更大，所以接下来拿走第 $5$ 个部分。
• 同样地，接下来比较第 $2$ 个和第 $4$ 个部分，由于第 $4$ 个更大，所以拿走第 $4$ 个部分。
• 接下来比较第 $2$ 个和第 $3$ 个部分，由于第 $2$ 个更大，所以拿走第 $2$ 个部分。
• 最后只剩下第 $3$ 个部分，所以拿走第 $3$ 个部分。

即拿取的顺序为： 第 $1$ 个 ($2$) $\to$ 第 $5$ 个 ($9$) $\to$ 第 $4$ 个 ($10$) $\to$ 第 $2$ 个 ($8$) $\to$ 第 $3$ 个 ($1$) （括号内为部分的大小）

由此，JOI 君拿到的部分是第 $1$ 个、第 $4$ 个和第 $3$ 个，大小之和为 $13$，因此第 $1$ 行输出 $13$。对于最开始拿走其他部分的情况，计算方法相同。