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