시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 74 43 23 65.714%

문제

베시는 스마트 폰 게임을 좋아한다. 현재 재미있게 하는 게임은 시작 할 때, 1~40 범위를 갖는 N(2≤N≤262,144)개의 정수가 주어지는데 연속된 두 수가 같으면 하나로 합칠 수 있는데 합칠 경우 기존 값보다 1이 큰 수를 만들 수 있다. (예를 들어, 7이 두 개 연속되어 있으면 8로 합칠 수 있다)
 
게임의 목표는 가장 큰 수를 만드는 것이다. 베시를 도와서 가능한 가장 큰 수를 만들 수 있게 하자.

입력

첫 번째 줄에 N이 입력된다. 두 번째 줄부터 N줄에 걸쳐 정수가 입력된다.

출력

만들 수 있는 가장 큰 수를 출력하라.

예제 입력

4
1
1
1
2

예제 출력

3

힌트

예로 주어진 1 1 1 2 는 2번째와 3번째 1을 합쳐서 2로 만들면 1 2 2 가 되고 2 두 개를 합치면 3이 될 수 있다. 그러므로 최대 값은 3이다. 만약에 1번째 2번째 1을 합치면 2 1 2 가 되는데 더 이상 합칠 게 없으므로 최대값은 2가 되므로 앞에서 한 방법이 최대값을 얻는 방법이다.