0447 - ダルマ落とし

あなたは，「ダルマ落とし」と呼ばれるゲームの一種を遊んでいる．

ゲームの開始時には，様々な重さの同じ大きさの木のブロックがいくつか，塔状に積んである． その上にはダルマを表すブロックがある． あなたは木槌を持っているが，その頭はブロック一つの高さよりより太く，二つ分よりは細い．

あなたは，一番上のダルマ以外の隣り合うブロック二つで重さの差が 1 以下の対のどれかを選び， 木槌の一撃で両方叩き出すことができる． その上にあったブロックは塔を崩さず真下に落ちる． 重さの差が 2 以上の対は，塔のバランスを保ったまま木槌を振り抜くのが難しいため，叩き出せない． 三つのブロックを同時に叩き出すのには超人的精度を要するので，到底無理だ．

ゲームの目標はできるだけ多くのブロックを取り除くことである． あなたの仕事は，最適な叩き出しの順序を選んだときに， 取り除けるブロックの個数を求めることである．

図D1. 二つのブロックを同時に叩き出す

上図のように，重さ 1, 2, 3, 1 の 4 ブロックが下からこの順で積んであるとき， 重さ 2 と 3 の中央のブロック二つを一度に叩き出すことができる． 上のブロックは下に落ちて，残るのは重さ 1 のブロック二つとダルマブロックになる． 残った重さ 1 のブロックの対は，さらに続けて叩き出すことができる．

入力は複数のデータセットからなる． データセットの数は 50 以下である． 各データセットは次の形式で表される．

n
w1 w2 … wn

n は一番上のダルマを除くブロックの個数を表す． n は，正の整数であり，300 を超えない． w_i は下から i 番目のブロックの重さを表す． w_i は整数であり，1 以上，1000 以下である．

入力の終わりは，1 個のゼロだけからなる行で表される．

各データセットについて，取り除くことができるブロックの最大個数を 1 行に出力せよ．

4
1 2 3 4
4
1 2 3 1
5
5 1 2 3 6
14
8 7 1 4 3 5 4 1 6 8 10 4 6 5
5
1 3 5 1 3
0

4
4
2
12
0