题目描述

有一排怪物站成一列，第 $i$ 只怪物的生命值为 $a_i$。

你准备释放一次连环雷击。这次雷击一共会命中恰好 $n$ 次，并且每只怪物都会被命中恰好一次。

在施法前，你需要先决定两件事：

• 选择哪一只怪物作为第一次被命中的怪物；
• 选择雷击的初始威力 $x$。

雷击的命中规则如下：

1. 第一次命中的一定是你事先选定的那只怪物。
2. 从第二次开始，每一次命中时，系统会在尚未被命中、并且与已被命中的某只怪物相邻的怪物中，随机选择一只作为下一次命中的目标。
3. 最终每只怪物都会被命中一次。

若某只怪物是第 $t$ 次被命中（第一次命中记为第 $1$ 次），则它受到的伤害为：

当怪物受到的伤害不小于它的生命值时，这只怪物会被消灭。

你可以自由选择第一次命中的位置，选定好后你希望无论中途如何随机，最终都能把所有怪物全部消灭。请你求出满足要求的最小初始威力 $x$ 是多少。

输入格式

第一行一个整数 $n$，表示怪物数量。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每只怪物的生命值。

输出格式

输出一个整数，表示最小初始威力。

6
2 1 5 6 4 3

8

Hint

样例解释： 一种最优选择是：第一次命中第 $4$ 只怪物，初始威力取 $x=8$。