Hide

Problem G
Heating Up

/problems/heatingup/file/statement/en/img-0001.jpg

Chilli pizza by Rahul Upadhyay, Unsplash

Jonas just entered his first chilli-eating contest. He is presented with a pizza consisting of $n$ slices, numbered from $1$ to $n$, each containing a selection of chilli peppers. Initially slices $i$ and $i+1$ are adjacent on the plate (where $1 \leq i < n$), and so are slices $1$ and $n$. According to the contest rules only one slice can be consumed at a time, and the slice must be finished in its entirety before a new slice is started. Jonas is allowed to pick any slice to eat first, but after that he is only allowed to eat slices that have at most one remaining adjacent slice.

The spiciness of each slice is measured in Scoville Heat Units (SHU). Jonas has a certain spiciness tolerance, also measured in SHU, which corresponds to the spiciness of the spiciest slice that Jonas can tolerate eating. He has also noticed that, after eating a slice of $k$ SHU, his tolerance immediately increases by $k$.

In order to win the contest, Jonas would like to finish all the slices of his pizza. Help him determine the minimum initial spiciness tolerance necessary to do so while abiding by the contest rules.

Input

The input consists of:

One line with an integer $n$ ($3 \le n \le 5 \cdot 10^{5}$), the number of pizza slices.
One line with $n$ integers $s_{1}, s_{2}, \ldots , s_{n}$ ($0 \le s_{i} \le 10^{13}$), where $s_ i$ is the spiciness of the $i$th slice in SHU.

Output

Output the minimum initial spiciness tolerance in SHU that Jonas needs in order to be able to eat all slices of the pizza.

Sample Input 1	Sample Output 1
5 5 0 10 6 1	4

Sample Input 2	Sample Output 2
7 20 23 7 2 3 7 1	2

Problem GHeating Up

Input

Output

Problem G
Heating Up