248 게임

Bessie는 손이 커서 작은 터치스크린을 다루기가 불편하지만, 휴대폰으로 하는 게임을 좋아한다.

요즘은 특히 한 게임에 빠져 있다. 이 게임은 1 이상 40 이하의 정수 $N$개로 시작한다 ($2 \le N \le 248$). Bessie는 값이 같은 두 인접한 수를 그보다 1 큰 수 하나로 바꿀 수 있다. 예를 들어 인접한 7 두 개는 8 하나가 된다. 합칠 수 있는 인접한 쌍이 더 이상 남지 않으면 게임이 끝난다. 목표는 게임이 끝났을 때 수열에 남은 가장 큰 수를 최대로 만드는 것이다. Bessie가 얻을 수 있는 가장 높은 점수를 구하여라.

첫째 줄에 $N$이 주어진다.

둘째 줄부터 $N$개의 줄에 게임 시작 시점의 수가 한 줄에 하나씩 순서대로 주어진다. 각 수는 1 이상 40 이하의 정수이다.

Bessie가 만들 수 있는 가장 큰 수를 한 줄에 출력한다.

수열이 1 1 1 2인 경우를 보자. 두 번째와 세 번째 1을 합쳐 2로 만들면 1 2 2가 되고, 뒤쪽의 2 두 개를 다시 합치면 1 3이 되어 3을 얻는다. 첫 번째와 두 번째 1을 먼저 합치면 최적해가 나오지 않는다.