24498번 - blobnom

문제

블롭들은 심심해서 서로를 이용해 $N$개의 탑을 만들었다. 각 탑의 높이는 그 탑에 있는 블롭의 수와 같다.

여러분은 다음 행동을 0ドル$회 이상 할 수 있다.

1. 처음과 마지막이 아닌 탑 중 하나를 선택한다. 단, 선택한 탑과 인접한 두 탑의 높이가 모두 1ドル$ 이상이어야 한다.
2. 선택한 탑과 인접한 두 탑에 있는 블롭을 한 마리씩 각각 땅에 내려놓는다. 즉, 인접한 두 탑의 높이가 모두 1ドル$만큼 감소한다.
3. 땅에 내려놓은 두 마리의 블롭 중 하나의 블롭만 1.에서 선택한 탑에 쌓는다. 즉, 선택한 탑의 높이가 1ドル$만큼 증가한다.

이 과정에서 이전에 인접하지 않았던 두 탑이 새롭게 인접하게 되지는 않는다. 채완이를 위해 만들 수 있는 가장 높은 탑의 높이를 구해 주자.

입력

첫째 줄에 탑의 개수 $N$이 주어진다.

둘째 줄에 각 탑의 높이 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

출력

문제의 정답을 출력한다.

제한

• 1ドル \le N \le 10^6$
• 1ドル \le A_i \le 10^9$ (1ドル \le i \le N$)

힌트