자유 이용권

문제

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

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

입력

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

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

출력

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

예제 입력 1

3
1 1 3

예제 출력 1

5

예제 입력 2

2
3 5

예제 출력 2

7

예제 입력 3

4
2 2 2 3

예제 출력 3

9