트리는 사이클이 없는 연결 그래프이다. 정점 N개로 이루어진 트리는 N-1개의 간선으로 이루어져 있다.</p>

트리의 두 정점 사이의 거리는 한 정점에서 다른 정점으로 갈 때, 지나는 간선 개수의 최솟값이다.

트리의 지름은 모든 두 정점 사이의 거리 중에서 가장 큰 값이다.

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

• 트리의 루트를 V라고 하자.
• V에서 가장 거리가 먼 정점과의 거리를 D라고 하자.
• 1보다 크거나 같고, D보다 작거나 같은 모든 i에 대해서, 거리가 i인 정점의 개수는 cnt[i] 이다.

cnt배열이 주어졌을 때, 만들 수 있는 트리 중에서 지름이 가장 큰 것의 지름을 출력하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 cnt 배열의 크기 N (1 ≤ N ≤ 50)이 주어진다.</p>

둘째 줄에는 cnt 배열의 값이 cnt[1]부터 cnt[N]까지 차례대로 주어진다. (1 ≤ cnt[i] ≤ 1000)

출력 형식

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

예제 입력 1

1
3

예제 출력 1

2

예제 입력 2

2
2 2

예제 출력 2

4

예제 입력 3

4
4 1 2 4

예제 출력 3

5

힌트

예제 1의 경우에 만들 수 있는 트리는 한 가지이다.</p>

예제 2의 경우에 다음과 같은 두 가지 트리를 만들 수 있다. 왼쪽 트리의 지름은 3, 오른쪽 트리의 지름은 4이다.

예제 3의 경우에는 아래 그림과 같은 트리를 만들 수 있다.