长期以来,科学家们研究鲨鱼的行为。与许多其他物种一样,鲨鱼会在某个位置进行短距离运动,并在不同位置之间进行长距离运动。
Max 是一位年轻的生物学家。在 $$$n$$$ 天里,他观察了一条特定的鲨鱼,现在他知道鲨鱼每天移动的距离。所有的距离都是不同的。麦克斯现在想知道鲨鱼去过多少个地方。他假设存在这样一个整数$$$k$$$,如果鲨鱼在某一天移动的距离严格小于$$$k$$$,那么它不会改变位置;否则,如果鲨鱼一天内移动的距离大于或等于 $$$k$$$;然后那天它改变了位置。请注意,鲨鱼有可能连续几天改变位置,其中每一天鲨鱼都移动了至少 $$$k$$$ 的距离。
鲨鱼离开后再也没有回到原来的位置。因此,在$$$n$$$天的序列中,当鲨鱼在每一天中移动的距离小于$$$k$$$时,我们可以找到连续的非空线段:每个这样的线段对应于一个位置。 Max想要选择这样的$$$k$$$,使得所有这些段的长度都相等。
找到这样的整数$$$k$$$,使得位置的数量尽可能大。如果有多个这样的$$$k$$$,则打印最小的一个。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 天数。
第二行包含 $$$n$$$ 不同的正整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 每天行驶的距离。
输出
打印单个整数 $$$k$$$,使得
1. 鲨鱼在每个地点停留的天数相同,
2. 满足第一个条件的位置数量是最大可能的,
3. $$$k$$$ 是满足第一个和第二个条件的最小可能值。
示例
输入 #1
8 1 2 7 3 4 8 5 6
输出 #1
7
输入 #2
6 25 1 2 3 14 36
输出 #2
2
注意
在第一个示例中,鲨鱼在第 $$$1$$$ 和 $$$2$$$ 天(第一个位置)在某个位置内移动,然后在第 $$$4$$$ 和第 $$$5$$$ 天(第二个位置),然后在第 $$$7$$$ 和第 $$$8$$$ 天(第三个位置)。总共有三个地点。
在第二个示例中,鲨鱼仅在第 $$$2$$$ 天在某个位置内移动,因此只有一个位置。