지름이 가장 긴 트리 만들기

트리는 사이클이 없는 연결 그래프다. 정점이 $N$개인 트리는 간선이 $N-1$개다.

두 정점 사이의 거리는 한 정점에서 다른 정점으로 갈 때 지나는 간선 개수의 최솟값이다. 트리의 지름은 모든 정점 쌍의 거리 중에서 가장 큰 값이다.

아래 조건을 만족하는 트리 중에서 지름이 가장 긴 것을 만들어 보자.

• 트리의 루트를 $V$라고 하자.
• $V$에서 가장 먼 정점까지의 거리를 $D$라고 하자.
• $1 \le i \le D$인 모든 $i$에 대해, $V$와의 거리가 정확히 $i$인 정점의 개수는 $cnt[i]$다.

$cnt$ 배열이 주어지면 조건을 만족하는 트리의 지름 중 최댓값을 출력한다.

첫째 줄에 $cnt$ 배열의 크기 $N$ ($1 \le N \le 50$)이 주어진다.

둘째 줄에 $cnt[1]$부터 $cnt[N]$까지 $N$개의 값이 차례대로 주어진다. ($1 \le cnt[i] \le 1000$)

조건을 만족하는 트리 중에서 지름이 가장 큰 것의 지름을 첫째 줄에 출력한다.