题目描述

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?

输入格式

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 the minimum possible value of $a_n$ in the resulting sequence.

5
6 3 5 5 2

10

3
2 1 100000

100002

提示

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.

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.