자유 이용권

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

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

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

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

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