P17044 [NWERC 2021] 辣度升温 / Heating Up

译自 [Northwestern Europe Regional Contest (NWERC) 2021](http://2021.nwerc.eu) 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。

【数据规模与约定】 对于所有数据，$3 \leq n \leq 5\cdot 10^5$；$0 \leq s_i \leq 10^{13}$。