acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem D

ダルマ落とし

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

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

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

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

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

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

Input

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

n
w1 w2wn

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

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

Output

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

Sample Input

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

Output for the Sample Input

4
4
2
12
0
(End of Problem D) A B C D E F G H