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