题目描述

JOI 君和 IOI 酱是双胞胎兄妹。JOI 君最近迷上了烘焙，今天他刚烤好一个蛋糕准备享用，但烤好的香味引来了 IOI 酱，于是两人决定平分这个蛋糕。

蛋糕是圆形的。从某一点沿放射状切入，将蛋糕切分成 $N$ 块，并按逆时针方向为这些块编号 $1$ 到 $N$。也就是说，对于 $1 \leq i \leq N$，第 $i$ 块与第 $i-1$ 块和第 $i+1$ 块相邻（其中视第 $0$ 块为第 $N$ 块，第 $N+1$ 块为第 $1$ 块）。第 $i$ 块的大小为 $A_i$，但由于切工十分拙劣，所有 $A_i$ 的值均互不相同。

:::align{center} :::

决定将这 $N$ 块蛋糕分给 JOI 君和 IOI 酱。分配方式如下：

• 首先由 JOI 君从 $N$ 块中选择 $1$ 块取走。
• 随后从 IOI 酱开始，IOI 酱和 JOI 君轮流从剩余蛋糕块中每次取 1 块。但（由于两人不擅长取蛋糕且要避免破坏蛋糕形状）只能取那些至少有一侧相邻蛋糕块已被取走的蛋糕块。当有多块可取的蛋糕块时，选择其中 最大 的一块取走。

JOI 君想知道，对于每一块蛋糕，若他最初选择取走该块，则最终自己获得的所有蛋糕块大小之和是多少。

任务

给定蛋糕块的数量 $N$ 以及 $N$ 块蛋糕的大小信息，编写程序计算对于每一块蛋糕，若最初取走该块，则 JOI 君最终获得的蛋糕块大小之和。

输入格式

从标准输入读取以下输入数据：

• 第 $1$ 行包含一个整数 $N$，表示蛋糕被切分为 $N$ 块。
• 后续 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含一个整数 $A_i$，表示第 $i$ 块蛋糕的大小。

输出格式

向标准输出输出 $N$ 行。第 $i$ 行（$1 \leq i \leq N$）输出一个整数，表示若最初取走第 $i$ 块蛋糕，则 JOI 君最终获得的蛋糕块大小之和。

5
2
8
1
10
9

13
18
12
13
12

提示

样例 1 解释

此示例对应题目中图示的情况。

例如，假设最初取走第 $1$ 块。此时：

• 剩余蛋糕块中「至少有一侧相邻蛋糕块已被取走」的是第 $2$ 块和第 $5$ 块，由于第 $5$ 块较大，因此接下来取走第 $5$ 块。
• 类似地，接下来比较第 $2$ 块和第 $4$ 块，由于第 $4$ 块较大，因此取走第 $4$ 块。
• 接着比较第 $2$ 块和第 $3$ 块，由于第 $2$ 块较大，因此取走第 $2$ 块。
• 最后仅剩第 $3$ 块，因此取走第 $3$ 块。

即蛋糕块的取走顺序为：

第 $1$ 块 ($2$) → 第 $5$ 块 ($9$) → 第 $4$ 块 ($10$) → 第 $2$ 块 ($8$) → 第 $3$ 块 ($1$)

（括号内为蛋糕块大小）

因此 JOI 君取走的蛋糕块为第 $1$、$4$、$3$ 块，其大小之和为 $13$，故在第 $1$ 行输出 $13$。最初取走第 $1$ 块以外的其他块时，也以类似方式计算。

限制

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

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

子任务

子任务 1 [10 分]

• 满足 $N \leq 5000$

子任务 2 [90 分]

无额外限制

翻译由 DeepSeek V3 完成