Description

有 N 堆从左往右依次排列的石子，每次可以按照以下两种方 式中的一种拿走石子： 1. 在任意一堆石子中拿走一颗石子； 2. 拿走最左端或者最右端石子堆的全部石子； 拿走若干次石子后，一定存在一个整数 k，使得剩余的石子 堆数为 2k-1，从左往右每堆石子的数量依次为 1，2，…，k - 1，k，k - 1，…，2，1。请计算 k 的最大值。 例如: N = 6，N 堆石子初始数量从左往右依次为 2，2，3，3， 2，1； 第 1 堆石子拿走一颗，所有石子堆为 1，2，3，3，2，1； 第 4 堆石子拿走一颗，所有石子堆为 1，2，3，2，2，1； 第 5 堆石子拿走一颗，所有石子堆为 1，2，3，2，1，1； 拿走最右端石子堆的全部石子，所有石子堆为 1，2，3， 2，1； 剩余石子堆 1，2，3，2，1，符合题目要求且没有更优的结 果，所以 k 为 3。

Format

Input

第一行包含一个正整数 N，表示初始石子的堆数； 第二行包含 N 个正整数 P1，P 2，…，Pn-1 ，Pn ，表示从左到 右每堆石子的数量，整数之间以一个空格隔开。

Output

一个整数，表示 k 的最大值。

Samples

6
2 2 3 3 2 1

3

Limitation

数据范围 测试点 1~10： 1≤N≤10⁵； 1≤P≤10⁵。