You have a sequence of $$$n$$$ integers $$$(a_1, a_2, \ldots, a_n)$$$, the initial values of which are given to you. You may apply the following operation to the sequence any number of times (possibly zero):

Choose an index $$$i$$$ ($$$1 \le i \le n$$$).
Choose a set $$$S$$$ to be either the prefix $$$\{1,2,\ldots,i-1\}$$$ or the suffix $$$\{i+1,i+2,\ldots,n\}$$$.
For every $$$j \in S$$$, replace $$$a_j$$$ with $$$2a_i - a_j$$$.

Your goal is to make the sequence non-decreasing and all elements positive, while minimizing $$$a_n$$$, using the operation above any number of times. That is, $$$1 \le a_1 \le a_2 \le \ldots \le a_n$$$ must hold in the resulting sequence. What is the minimum possible value of $$$a_n$$$ in the resulting sequence?

Input

The first line of input contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$).

The second line contains $$$n$$$ integers representing the initial values of $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Output

Output the minimum possible value of $$$a_n$$$ in the resulting sequence.

Note

Explanation for the sample input/output #1

You can do the following sequence of operations.

Choose $$$i = 1$$$ and $$$S$$$ as the suffix $$$\{2, 3, 4, 5\}$$$: $$$(6, 3, 5, 5, 2) \to (6, 9, 7, 7, 10)$$$.
Choose $$$i = 3$$$ and $$$S$$$ as the prefix $$$\{1, 2\}$$$: $$$(6, 9, 7, 7, 10) \to (8, 5, 7, 7, 10)$$$.
Choose $$$i = 2$$$ and $$$S$$$ as the prefix $$$\{1\}$$$: $$$(8, 5, 7, 7, 10) \to (2, 5, 7, 7, 10)$$$.

After these operations, the sequence is non-decreasing and all elements are positive. It can be shown that $$$a_5=10$$$ is the minimum possible value.

Explanation for the sample input/output #2

The minimum possible value of $$$a_3$$$ is $$$100002$$$, which can be attained by the following operations.

Choose $$$i = 2$$$ and $$$S$$$ as the suffix $$$\{3\}$$$: $$$(2, 1, 100000) \to (2, 1, -99998)$$$.
Choose $$$i = 1$$$ and $$$S$$$ as the suffix $$$\{2, 3\}$$$: $$$(2, 1, -99998) \to (2, 3, 100002)$$$.

Note that the sequence may contain non-positive values during operations.

Reflect Sort

Examples