分数: 900 点
问题陈述
AtCoder先生为他做了一个圆形的巧克力蛋糕 2N 朋友们。它从中心径向切割成 2N 等份,编号 0 通过 2N-1 按顺时针顺序。
为了进行最后的润色,他将在每件作品上放上草莓。他已经听到了他的朋友们对此的看法。朋友已数完 0 通过 2N-1和朋友 i (0 \leq i \leq 2N-1) 想要以下内容:
- 一块 i, i+1, \dots, i+N-1 总共至少有 A_i 上面有草莓(用于 x \geq 2N,考虑一块 x 作为一块 x-2N).
为了满足所有朋友的要求,整个蛋糕上至少应该放多少个草莓?
约束
- 1 \leq N \leq 150000
- 0 \leq A_i \leq 5 \times 10^8 \ (0 \leq i \leq 2N-1)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_0 A_1 \cdots A_{2N-1}
输出
打印出整个蛋糕上应该放置的最少草莓数量,以满足朋友们的要求。
样本输入 1
3 2 5 7 4 2 1
示例输出 1
8
考虑我们提出的情况 1, 0, 1, 4, 2, 0 草莓碎片 0, 1, 2, 3, 4, 5。
这种情况下,好友的所有请求均已满足,如下:
- 朋友 0:碎片 0, 1, 2 共有 2 上面有草莓,不少于 A_0 = 2.
- 朋友 1:碎片 1, 2, 3 共有 5 上面有草莓,不少于 A_1 = 5.
- 朋友 2:碎片 2, 3, 4 共有 7 上面有草莓,不少于 A_2 = 7.
- 朋友 3:碎片 3, 4, 5 共有 6 上面有草莓,不少于 A_3 = 4.
- 朋友 4:碎片 4, 5, 0 共有 3 上面有草莓,不少于 A_4 = 2.
- 朋友 5:碎片 5, 0, 1 共有 1 上面有草莓,不少于 A_5 = 1.
因此,我们可以通过总共放置 8 蛋糕上的草莓。 这是所需的最少草莓数量。
示例输入 2
3 8 0 6 0 9 0
示例输出 2
12
考虑我们提出的情况 6, 0, 2, 1, 3, 0 草莓碎片 0, 1, 2, 3, 4, 5。
这种情况下,好友的所有请求均已满足,如下:
- 朋友 0:碎片 0, 1, 2 共有 8 上面有草莓,不少于 A_0 = 8.
- 朋友 1:碎片 1, 2, 3 共有 3 上面有草莓,不少于 A_1 = 0.
- 朋友 2:碎片 2, 3, 4 共有 6 上面有草莓,不少于 A_2 = 6.
- 朋友 3:碎片 3, 4, 5 共有 4 上面有草莓,不少于 A_3 = 0.
- 朋友 4:碎片 4, 5, 0 共有 9 上面有草莓,不少于 A_4 = 9.
- 朋友 5:碎片 5, 0, 1 共有 6 上面有草莓,不少于 A_5 = 0.
因此,我们可以通过总共放置 12 蛋糕上的草莓。 这是所需的最少草莓数量。
示例输入 3
5 3 1 5 7 0 8 4 6 4 9
示例输出 3
12
我们可以把 0, 0, 0, 4, 0, 1, 1, 1, 0, 5 草莓碎片 0, 1, \dots, 9分别满足朋友们的所有要求。
在这种情况下,总共有 12 蛋糕上的草莓,这是最少需要的草莓数量。
示例输入 4
1 267503 601617
示例输出 4
869120
我们可以把 267503 草莓片 0 和 601617 草莓片 1 满足朋友们的所有要求。
示例输入 5
8 418940906 38034755 396064111 43044067 356084286 61548818 15301658 35906016 20933120 211233791 30314875 25149642 42550552 104690843 81256233 63578117
示例输出 5
513119404