背景

译自 Northwestern Europe Regional Contest (NWERC) 2021 Problem H。

原题许可协议为 CC BY-SA。

题目描述

Jonas 刚刚参加了他的第一场吃辣椒比赛。摆在他面前的是一张披萨，它由 $n$ 块组成，编号从 $1$ 到 $n$，每一块都含有一些辣椒。最初，盘子上第 $i$ 块和第 $i+1$ 块相邻（其中 $1 \leq i < n$），第 $1$ 块和第 $n$ 块也相邻。根据比赛规则，每次只能吃一块披萨，并且必须把这一块完整吃完后，才能开始吃新的块。Jonas 可以选择任意一块作为第一块来吃，但在那之后，他只能吃至多还有一个剩余相邻块的披萨块。

每块披萨的辣度用史高维尔辣度单位（SHU）衡量。Jonas 有一个同样以 SHU 衡量的辣度耐受值，它对应于 Jonas 能够忍受吃下的最辣披萨块的辣度。他还注意到，在吃下一块辣度为 $k$ SHU 的披萨后，他的耐受值会立即增加 $k$。

为了赢得比赛，Jonas 想吃完整张披萨。请帮助他确定，在遵守比赛规则的前提下，他完成整张披萨所需的最小初始辣度耐受值。

输入格式

输入包含：

• 一行一个整数 $n$（$3 \leq n \leq 5\cdot 10^5$），表示披萨块数。
• 一行 $n$ 个整数 $s_1,s_2,\ldots,s_n$（$0 \leq s_i \leq 10^{13}$），其中 $s_i$ 表示第 $i$ 块披萨的辣度，单位为 SHU。

输出格式

输出 Jonas 为了能够吃完整张披萨所需的最小初始辣度耐受值，单位为 SHU。

5
5 0 10 6 1

4

7
20 23 7 2 3 7 1

2

提示

【数据规模与约定】

对于所有数据，$3 \leq n \leq 5\cdot 10^5$；$0 \leq s_i \leq 10^{13}$。