题目描述

你有一个包含 $n$ 个整数的序列 $(a_1, a_2, \ldots, a_n)$，它们的初始值已知。你可以对该序列进行任意次数（包括零次）如下操作：

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

你的目标是，经过若干次上述操作后，使该序列单调不降且所有元素均为正数，同时使 $a_n$ 的值最小。即最终序列满足 $1 \le a_1 \le a_2 \le \ldots \le a_n$。请你输出操作后 $a_n$ 的最小可能值。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 100\,000$）。

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

输出格式

输出一个整数，表示最终序列中 $a_n$ 的最小可能值。

5
6 3 5 5 2

10

3
2 1 100000

100002

提示

样例输入输出 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 的解释

最终 $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)$。

注意，操作过程中序列的元素可以为非正数。

由 ChatGPT 5 翻译