일렬로 배치된 \(N\)개의 보관소에 GOLD 덩어리가 쌓여 있다. 처음에 \(i\)번째 보관소에 들어 있는 GOLD 덩어리의 수는 \(A_i\)이다.

다음 주조 작업을 0번 이상 수행할 수 있다.

1. 첫 번째와 마지막이 아닌 보관소 하나를 선택한다.
2. 선택한 보관소의 양옆 보관소에서 GOLD 덩어리를 하나씩 꺼낸다.
3. 꺼낸 두 덩어리를 녹여 하나의 새로운 GOLD 덩어리로 만든 뒤, 선택한 보관소에 넣는다.

양옆 보관소에 GOLD 덩어리가 하나 이상 있을 때만 해당 보관소를 선택할 수 있다. 한 번의 작업이 끝나면 선택한 보관소의 GOLD 덩어리는 1개 늘어나고, 양옆 보관소의 GOLD 덩어리는 각각 1개 줄어든다.

작업을 적절히 수행했을 때, 하나의 보관소에 들어 있을 수 있는 GOLD 덩어리 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보관소의 수 \(N\)이 주어진다.

둘째 줄에 각 보관소에 처음 들어 있는 GOLD 덩어리의 수 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

출력

작업을 0번 이상 수행한 뒤 하나의 보관소에 들어 있을 수 있는 GOLD 덩어리 수의 최댓값을 출력한다.

제한 사항

• \(3 \le N \le 300,000\)
• \(0 \le A_i \le 1,000,000,000\)

예제 입력 1

5
2 1 3 4 2

예제 출력 1

6

예제 설명 1

네 번째 보관소를 선택하여 작업을 두 번 수행할 수 있다.

2 1 3 4 2
2 1 2 5 1
2 1 1 6 0

따라서 네 번째 보관소에 GOLD 덩어리를 6개 모을 수 있다.