시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 101 45 34 41.975%

문제

Bessie는 큰 손으로 작은 터치스크린을 다루는 것이 불편함에도 불구하고 휴대폰으로 게임을 하는 것을 좋아한다.

그녀는 특히 요즘 하고있는 게임에 흥미를 느끼고 있다. 이 게임은 N개의 양수들(2<=N<=248)로 시작되며, 각 수는 1에서 40 사이이다. 각 수에서 Bessie는 같은 값을 가진 두개의 인접한 수를 그보다 1 큰 수 한개로 바꿀 수 있다. (예를 들어, 그녀는 두 개의 인접한 7을 8로 바꿀 수 있다.) 목표는 게임에서 가장 마지막에 남는 수의 값을 최대화하는 것이다. Bessie가 가능한 가장 높은 점수를 얻을 수 있도록 도와주어라!

입력

첫째 줄에는 N을 입력받는다.

2번째 줄부터 N개의 줄에는 게임의 시작에서 주어지는 N개의 숫자를 입력받는다.

출력

Bessie가 만들 수 있는 가장 큰 정수를 출력해라.

예제 입력

4
1
1
1
2

예제 출력

3

힌트

이 예에서, Bessie는 두번째와 세번째에 있는 1을 2로 합친다. (1 2 2)

두번째와 세번째에 있는 2를 3으로 합친다. (1 3)

첫번째와 두번째 1을 합치는 것은 최적해가 아님을 주의해라.