Daruma Otoshi

You are playing a variant of the game Daruma Otoshi (Dharma block striking).

At the start of a game, several wooden blocks of the same size but of varying weights are stacked on top of each other into a tower. One more block standing for Dharma sits on top. You hold a wooden hammer whose head is thicker than the height of one block but thinner than two blocks.

You can choose any two adjacent blocks other than the Dharma block on top whose weights differ by at most 1, and push both of them out of the stack with a single blow of the hammer. The blocks above the removed pair then fall straight down and the tower does not collapse. You cannot strike a pair whose weights differ by 2 or more, because pushing such a pair out while keeping the tower balanced is too hard. Striking three blocks out at once is impossible, since it would take superhuman accuracy.

The goal is to remove as many blocks as you can. Compute the number of blocks that can be removed when the blows are made in the best possible order.

Figure D1. Striking out two blocks at a time

In the figure above, four blocks weighing 1, 2, 3, and 1 from the bottom are stacked. You can strike out the middle two blocks, weighing 2 and 3. The blocks above then fall down, and two blocks of weight 1 plus the Dharma block remain. After that you can push out the remaining pair of weight-1 blocks.

The input consists of several datasets, at most 50 of them. Each dataset has the following format.

n
w1 w2 ... wn

$n$ is the number of blocks, not counting the Dharma block on top, and is a positive integer at most 300. $w_i$ is the weight of the $i$-th block counted from the bottom, an integer between 1 and 1000, inclusive.

A line containing a single zero marks the end of the input.

For each dataset, print on one line the largest number of blocks you can remove.