25635번 - 자유 이용권

문제

자유 이용권은 놀이공원의 모든 놀이기구를 횟수의 제한 없이 마음껏 이용할 수 있는 이용권이다. 준원이는 ANA 놀이공원의 자유 이용권을 구매했고, 최대한 많이 놀이기구를 이용할 생각이다. 단, 연속으로 같은 놀이기구를 이용하지는 않기로 했다.

그런데 준원이가 구매한 자유 이용권을 잘 살펴보니 놀이공원의 모든 놀이기구별로 이용 횟수의 제한이 명시되어 있었다. 이 자유 이용권으로, 연속으로 같은 놀이기구를 이용하지 않고 놀이기구를 이용할 수 있는 최대 횟수는 얼마일까?

입력

첫째 줄에 놀이기구의 종류의 개수 $N(1\le N \le 100\ 000)$이 주어진다.

둘째 줄에 정수 $a_1, a_2, ..., a_N$이 주어진다. $a_i(1 \le a_i \le 10^9)$는 $i$번째 놀이기구 이용 횟수 제한이다.

출력

연속으로 같은 놀이기구를 이용하지 않고 놀이기구를 이용할 수 있는 최대 횟수를 출력한다.

제한

힌트