您有一个 $$$n$$$ 整数 $$$(a_1, a_2, \ldots, a_n)$$$ 序列,其初始值已提供给您。您可以对序列应用以下操作任意次数(可能为零):
- 选择索引 $$$i$$$ ($$$1 \le i \le n$$$)。
- 选择一个集合 $$$S$$$ 作为前缀 $$$\{1,2,\ldots,i-1\}$$$ 或后缀 $$$\{i+1,i+2,\ldots,n\}$$$。
- 对于 S$$$ 中的每个 $$$j,将 $$$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 的说明
您可以执行以下操作顺序。
- 选择 $$$i = 1$$$ 和 $$$S$$$ 作为后缀 $$$\{2, 3, 4, 5\}$$$: $$$(6, 3, 5, 5, 2) \to (6, 9, 7, 7, 10)$$$。
- 选择 $$$i = 3$$$ 和 $$$S$$$ 作为前缀 $$$\{1, 2\}$$$: $$$(6, 9, 7, 7, 10) \to (8, 5, 7, 7, 10)$$$。
- 选择 $$$i = 2$$$ 和 $$$S$$$ 作为前缀 $$$\{1\}$$$: $$$(8, 5, 7, 7, 10) \to (2, 5, 7, 7, 10)$$$。
经过这些操作,序列是非递减的,并且所有元素都是正数。可以证明 $$$a_5=10$$$ 是最小可能值。
示例输入/输出#2 的说明
$$$a_3$$$ 的最小可能值为$$$100002$$$,可以通过以下操作获得。
- 选择 $$$i = 2$$$ 和 $$$S$$$ 作为后缀 $$$\{3\}$$$: $$$(2, 1, 100000) \to (2, 1, -99998)$$$。
- 选择 $$$i = 1$$$ 和 $$$S$$$ 作为后缀 $$$\{2, 3\}$$$: $$$(2, 1, -99998) \to (2, 3, 100002)$$$。
请注意,序列在操作期间可能包含非正值。