Special Pyramids

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

I can almost guarantee that this problem does not have a solution for the current constraints.

yeah it turns out my solution is wrong and i got a few counter cases for it , so i guess i will have to discard this problem or modify it.

Actually, you can think this problem as solving knapsack which is not so easy to solve for the given constraints.

//