Reflect Sort

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):

1. Choose an index \(i\) (\(1 \le i \le n\)).
2. Choose a set \(S\) to be either the prefix \(\{1, 2, \ldots, i-1\}\) or the suffix \(\{i+1, i+2, \ldots, n\}\).
3. 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.

5
6 3 5 5 2

10

Explanation for the sample input/output #1

You can do the following sequence of operations.

1. Choose \(i = 1\) and \(S\) as the suffix \(\{2, 3, 4, 5\}\): \((6, 3, 5, 5, 2) \to (6, 9, 7, 7, 10)\).
2. Choose \(i = 3\) and \(S\) as the prefix \(\{1, 2\}\): \((6, 9, 7, 7, 10) \to (8, 5, 7, 7, 10)\).
3. 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.

3
2 1 100000

100002

Explanation for the sample input/output #2

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

1. Choose \(i = 2\) and \(S\) as the suffix \(\{3\}\): \((2, 1, 100000) \to (2, 1, -99998)\).
2. 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.