다루마 오토시

다루마 오토시를 변형한 게임을 한다.

게임을 시작하면 크기는 같고 무게는 서로 다를 수 있는 나무 블록 여러 개가 위로 쌓여 탑을 이룬다. 맨 위에는 다루마를 뜻하는 블록이 하나 더 놓인다. 손에는 나무망치가 있고, 망치 머리의 두께는 블록 하나의 높이보다 두껍지만 두 배보다는 얇다.

맨 위의 다루마를 뺀 나머지 중에서 서로 붙어 있고 무게 차이가 1 이하인 블록 두 개를 골라, 망치로 한 번 쳐서 탑 밖으로 밀어낼 수 있다. 밀려난 자리 위에 있던 블록은 탑이 무너지지 않은 채 그대로 곧장 내려온다. 무게 차이가 2 이상인 두 블록은 균형을 잡으면서 밀어내기가 너무 어려워 칠 수 없다. 한 번에 세 개를 쳐내는 것은 사람의 정확도로는 불가능하다.

게임의 목표는 블록을 최대한 많이 없애는 것이다. 망치질 순서를 가장 좋게 정했을 때 없앨 수 있는 블록의 개수를 구하라.

그림 D1. 한 번에 두 블록을 쳐내는 모습

위 그림에서는 아래에서부터 무게가 1, 2, 3, 1인 블록 네 개가 쌓여 있다. 가운데의 무게 2와 3인 두 블록을 쳐내면 위에 있던 블록이 내려와 무게 1인 블록 두 개와 다루마 블록만 남는다. 그다음 남은 무게 1인 두 블록도 마저 밀어낼 수 있다.

입력은 여러 개의 데이터 집합으로 이루어지고, 데이터 집합은 최대 50개이다. 각 데이터 집합의 형식은 다음과 같다.

n
w1 w2 ... wn

$n$은 맨 위의 다루마를 뺀 블록의 개수이고, 300 이하의 양의 정수이다. $w_i$는 아래에서 $i$번째 블록의 무게이고, 1 이상 1000 이하의 정수이다.

입력의 끝은 0 하나만 있는 줄로 나타낸다.

각 데이터 집합마다 없앨 수 있는 블록 개수의 최댓값을 한 줄에 출력한다.