给你一个由 $n$ 个整数组成的序列 $(a_1, a_2, \dots, a_n)$，其初始值已给出。你可以对该序列进行以下操作任意次（可能为零次）：

• 选择一个下标 $i$ ($1 \le i \le n$)。
• 选择一个集合 $S$，它可以是前缀 $\{1, 2, \dots, i - 1\}$ 或后缀 $\{i + 1, i + 2, \dots, n\}$。
• 对于每个 $j \in S$，将 $a_j$ 替换为 $2a_i - a_j$。

你的目标是通过上述操作，使序列单调不降且所有元素均为正数，同时最小化 $a_n$。也就是说，在最终的序列中必须满足 $1 \le a_1 \le a_2 \le \dots \le a_n$。求最终序列中 $a_n$ 的最小可能值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)。

第二行包含 $n$ 个整数，表示 $a_1, a_2, \dots, a_n$ 的初始值 ($1 \le a_i \le 10^9$)。

输出格式

输出最终序列中 $a_n$ 的最小可能值。

样例

输入样例 1

5
6 3 5 5 2

输出样例 1

10

样例说明 1

你可以进行以下操作序列：

1. 选择 $i = 1$ 且 $S$ 为后缀 $\{2, 3, 4, 5\}$：$(6, 3, 5, 5, 2) \to (6, 9, 7, 7, 10)$。
2. 选择 $i = 3$ 且 $S$ 为前缀 $\{1, 2\}$：$(6, 9, 7, 7, 10) \to (8, 5, 7, 7, 10)$。
3. 选择 $i = 2$ 且 $S$ 为前缀 $\{1\}$：$(8, 5, 7, 7, 10) \to (2, 5, 7, 7, 10)$。

在这些操作之后，序列单调不降且所有元素均为正数。可以证明 $a_5 = 10$ 是最小可能值。

输入样例 2

3
2 1 100000

输出样例 2

100002

样例说明 2

$a_3$ 的最小可能值为 $100002$，可以通过以下操作达到：

1. 选择 $i = 2$ 且 $S$ 为后缀 $\{3\}$：$(2, 1, 100000) \to (2, 1, -99998)$。
2. 选择 $i = 1$ 且 $S$ 为后缀 $\{2, 3\}$：$(2, 1, -99998) \to (2, 3, 100002)$。

注意，在操作过程中，序列中可能会出现非正数。