Tree with the longest diameter

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.

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$)

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