Tree with the longest diameter

Interview

Time limit2sMemory limit512 MB

Summary

Given the number of vertices at each level from the root, build a tree realizing those level counts with the maximum possible diameter.

Level: Medium5 of 10
Topics: Tree, Greedy, Implementation, Graph
Solved: No attempts yet

Problem

A tree is a connected graph with no cycle. A tree with $N$ vertices has $N-1$ edges.

The distance between two vertices is the smallest number of edges on a path from one vertex to the other. The diameter of a tree is the largest distance over all pairs of vertices.

Build a tree with the longest possible diameter under the conditions below.

Call the root of the tree $V$ .
Call the distance from $V$ to the farthest vertex $D$ .
For every $i$ with $1 \le i \le D$ , the number of vertices whose distance from $V$ is exactly $i$ is $cnt[i]$ .

Given the array $cnt$ , print the largest diameter among the trees that satisfy the conditions.

Input

The first line has $N$ , the size of the array $cnt$ ( $1 \le N \le 50$ ).

The second line has the $N$ values $cnt[1]$ through $cnt[N]$ in order. ( $1 \le cnt[i] \le 1000$ )

Output

Print on the first line the diameter of the tree with the largest diameter among the trees that satisfy the conditions.

Examples5

Example 1
Input
```
1
3
```
Expected output
```
2
```
Example 2
Input
```
2
2 2
```
Expected output
```
4
```
Example 3
Input
```
4
4 1 2 4
```
Expected output
```
5
```
Example 4
Input
```
2
1 1
```
Expected output
```
2
```
Example 5
Input
```
3
1 1000 1
```
Expected output
```
3
```