Jonas 刚刚参加了他的第一场吃辣椒比赛。他面前有一张由 $n$ 片披萨组成的披萨，编号从 $1$ 到 $n$，每一片上都含有一定量的辣椒。最初，第 $i$ 片和第 $i+1$ 片在盘子上是相邻的（其中 $1 \le i < n$），第 $1$ 片和第 $n$ 片也是相邻的。根据比赛规则，一次只能吃一片披萨，并且必须在开始吃下一片之前将当前这一片完全吃完。Jonas 可以选择先吃任意一片，但在此之后，他只允许吃那些至多剩下一片相邻披萨的披萨片。

Chilli pizza by Rahul Upadhyay, Unsplash

每一片披萨的辣度以史高维尔指标（SHU）衡量。Jonas 有一定的辣度耐受力（同样以 SHU 衡量），这对应于他所能忍受的最辣的披萨片的辣度。他还注意到，在吃掉一片辣度为 $k$ SHU 的披萨后，他的耐受力会立即增加 $k$。

为了赢得比赛，Jonas 希望吃掉所有的披萨片。请帮助他确定在遵守比赛规则的前提下，他所需的最小初始辣度耐受力。

输入格式

输入包含： 一行包含一个整数 $n$ ($3 \le n \le 5 \cdot 10^5$)，表示披萨片的数量。 一行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$ ($0 \le s_i \le 10^{13}$)，其中 $s_i$ 表示第 $i$ 片披萨的辣度（单位为 SHU）。

输出格式

输出 Jonas 为了吃掉所有披萨片所需的最小初始辣度耐受力（单位为 SHU）。

样例

输入格式 1

5
5 0 10 6 1

输出格式 1

4

输入格式 2

7
20 23 7 2 3 7 1

输出格式 2

2