A pyramid of height N is defined as a structure with N blocks at the base , N - 1 blocks above it , N - 2 blocks above that … with 1 block at the top.

In this problem we will be dealing with Pyramids of special types where at a particular level , all blocks must be of same color.

Given N , the number of different colors of blocks and an array of size N , where the element array[i] denotes there are array[i] blocks of color i.

Print the maximum height of special pyramid you can get.

Constraints

1 <= N <= 100,000

1 <= array[i] <= 1,000,000,000

Sample

Input

2

2 4

Output

3

Explaination

Let ‘1’ denote blocks of color 1 and ‘2’ denote the blocks of color 2

```
The pyramid is
2
1 1
2 2 2
```

Input

3

3 4 4

Output

4

Explaination

```
Some of the possible pyramids are
1
1 1
2 2 2
3 3 3 3
or
3
3 3
1 1 1
2 2 2 2
All the possible pyramids have a height of atmost 4 so the answer is 4
```

Input

4

1 1 4 4

Output

3