Problem:
Daruma Otoshi You are playing a variant of a game called "Daruma Otoshi (Dharma Block Striking)". At the start of a game, several wooden blocks of the same size but with varying weights
are stacked on top of each other, forming a tower.
Another block symbolizing Dharma is placed atop.
You have a wooden hammer with its head thicker than the height of a block,
but not twice that. You can choose any two adjacent blocks, except Dharma on the top,
differing at most 1 in their weight,
and push both of them out of the stack with a single blow of your hammer.
The blocks above the removed ones then fall straight down,
without collapsing the tower.

You cannot hit a block pair with weight difference of 2 or more,
for that makes too hard to push out blocks while keeping the balance of the tower.
There is no chance in hitting three blocks out at a time,
for that would require superhuman accuracy. The goal of the game is to remove as many blocks as you can.
Your task is to decide the number of blocks that can be removed
by repeating the blows in an optimal order.   Figure D1. Striking out two blocks at a time  In the above figure, with a stack of four blocks weighing 1, 2, 3, and
1, in this order from the bottom, you can hit middle
two blocks, weighing 2 and 3, out from the stack.  The blocks above will
then fall down, and two blocks weighing 1 and the Dharma block will remain.
You can then push out the remaining pair of weight-1 blocks after that. Input The input consists of multiple datasets.
The number of datasets is at most 50.
Each dataset is in the following format.  n   w 1  w 2 … w n    n is the number of blocks, except Dharma on the top. n is a positive integer not exceeding 300. w i gives the weight of the i -th block counted from the bottom. w i is an integer between 1 and 1000, inclusive. The end of the input is indicated by a line containing a zero. Output For each dataset, output in a line the maximum number of blocks you can remove. 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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n):
        a = LI()
        l = len(a)
        s = set()
        r = 0
        for i in range(l-1):
            if abs(a[i] - a[i+1]) < 2:
                s.add((i,i+1))
        for i in range(4, l+1):
            for j in range(l-i+1):
                k = j + i - 1
                if (j+1, k-1) in s and abs(a[j] - a[k]) < 2:
                    s.add((j,k))
                    continue
                for m in range(j+2,k,2):
                    if (j,m-1) in s and (m,k) in s:
                        s.add((j,k))
                        break

        m = {}
        m[l] = 0
        def _f(i):
            if i in m:
                return m[i]
            r = 0
            for j in range(i,l+1):
                t = _f(j+1)
                if (i,j) in s:
                    t += j - i + 1
                if r < t:
                    r = t
            m[i] = r
            return r
        return _f(0)

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))



print(main())

Solution (Python):
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    wlst = list(map(int, input().split()))
    connect = [[None] * n for _ in range(n)]
    for i in range(n):
      for j in range(n):
        connect[i][j] = abs(wlst[i] - wlst[j]) <= 1
    
    max_lst = [[False] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
      max_lst[0][i] = True
    
    dp = [[0] * n for _ in range(n + 1)]
    
    def check(length, left):
      ret = dp[length - 1][left]
      for k in range(length - 1, 0, -2):
        if not max_lst[length - k - 1][left + k]:continue
        if connect[left + k - 1][left + length - 1]:
          temp = length - k + 1 + dp[k - 1][left]
          if ret < temp:
            ret = temp
      return ret
    
    for length in range(2, n + 1):
      for left in range(n - length + 1):
        dp[length][left] = check(length, left)
        if dp[length][left] == length:
          max_lst[length][left] = True
    
    print(dp[n][0])

main()

Solution (Python):
def isvalid(a, b):
    return abs(a - b) < 2
while 1:
    n = input()
    if n==0:
        break
    W = map(int, raw_input().split())
    dp = [[0]*n for i in xrange(n)]
    for i in xrange(n-1):
        if isvalid(W[i], W[i+1]):
            dp[i][i+1] = 1
    for l in xrange(1, n+1):
        for j in xrange(n-l):
            i = j+l
            
            if j+2 < i and isvalid(W[j], W[j+1]) and dp[j+2][i]:
                
                dp[j][i] = 1
            elif j < i-2 and isvalid(W[i-1], W[i]) and dp[j][i-2]:
                
                dp[j][i] = 1
            elif j+1 < i-1 and isvalid(W[j], W[i]) and dp[j+1][i-1]:
                
                dp[j][i] = 1
            else:
                
                for k in xrange(j+1, i-1):
                    if dp[j][k] and dp[k+1][i]:
                        dp[j][i] = 1
                        break
    res = [0]*n
    for i in xrange(n):
        r = res[i-1]
        for j in xrange(i):
            if dp[j][i]:
                r = max(r, res[j-1]+(i-j+1))
        res[i] = r
    print res[n-1]

Solution (Python):
import sys
input = sys.stdin.readline

ans = []
while True:
    N = int(input())
    if N == 0: break
    W = list(map(int, input().split()))
    
    dp = [[False]*N for _ in range(N)]
    for i in range(N-1):
        if abs(W[i]-W[i+1]) <= 1:
            dp[i][i+1] = True
    for d in range(4, N+1):
        for i in range(N-d+1):
            j = i+d-1
            for k in range(i, j):
                if dp[i][k] and dp[k+1][j]:
                    dp[i][j] = True
            if abs(W[i]-W[j]) <= 1 and dp[i+1][j-1]:
                dp[i][j] = True
    
    dp2 = [0]*(N+1)
    for i in range(N):
        for j in range(i+1, N):
            if dp[i][j]:
                dp2[j+1] = max(dp2[j+1], dp2[i]+j-i+1)
        dp2[i+1] = max(dp2[i+1], dp2[i])
    ans.append(dp2[N])
print(*ans, sep="\n")

Solution (Python):
def solve(n,w):
    dp=[[0]*(n+1) for _ in range(n+1)]
    for kukan in range(2,n+1):
        for l in range(0,n+1-kukan):
            r=l+kukan
            
            if (kukan-2)%2==0:
                if abs(w[l]-w[r-1])<=1 and dp[l+1][r-1]==r-l-2:
                    dp[l][r]=dp[l+1][r-1]+2
                    continue
            for i in range(l+1,r):
                if dp[l][r]<(dp[l][i]+dp[i][r]):
                    dp[l][r]=dp[l][i]+dp[i][r]
    return dp[0][n]
            

n=int(input())
while(n!=0):
    w=list(map(int,input().split()))
    print(solve(n,w))
    n=int(input())

Solution (Python):
def solve(n,lst):
    
    dp=[[0]*n for _ in range(n+1)]

    
    for j in range(n-1):
        if abs(lst[j]-lst[j+1])<=1 : dp[2][j]=2
    

    
    for i in range(3,n+1):
        for j in range(n-i+1):
            mx=0
            if i%2==0:
                if abs(lst[j]-lst[j+i-1])<=1:
                    if dp[i-2][j+1]==i-2:
                        dp[i][j]=i
                        continue
                mx=dp[i-2][j+1]                
                for k in range(2,i,2):
                    if mx<dp[k][j]+dp[i-k][j+k]:
                        mx=dp[k][j]+dp[i-k][j+k]
                        if mx==i:break
            else :
                for k in range(1,i,2):
                    if mx<dp[k][j]+dp[i-k][j+k]:
                        mx=dp[k][j]+dp[i-k][j+k]                
            dp[i][j]=mx
    print(dp[n][0])        
    

                

while 1:
    n=int(input())
    if n==0 : break
    lst=tuple(map(int,input().split()))
    solve(n,lst)

Solution (Python):
import sys


def main():
    while True:
        n = int(input())

        
        if n == 0:
            sys.exit()

        arr = list(map(int, input().split()))

        
        dp = [[0] * n for _ in range(n)]

        
        for d in range(1, n):

            
            for l in range(n - d):

                
                r = l + d

                
                if d % 2 == 1:

                    
                    if dp[l + 1][r - 1] == d - 1 and abs(arr[l] - arr[r]) <= 1:
                        dp[l][r] = dp[l + 1][r - 1] + 2

                    
                    else:
                        for k in range(l + 1, r):
                            tmp = dp[l][k] + dp[k + 1][r]
                            if tmp > dp[l][r]:
                                dp[l][r] = tmp

                
                else:
                    dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])

        print(dp[0][-1])


if __name__ == '__main__':
    main()

Solution (Python):
def solve(n,lst):
    
    dp=[[0]*n for _ in range(n+1)]

    
    for j in range(n-1):
        if abs(lst[j]-lst[j+1])<=1 : dp[2][j]=2
    

    
    for i in range(3,n+1):
        for j in range(n-i+1):
            mx=0
            if i%2==0:
                if abs(lst[j]-lst[j+i-1])<=1:
                    if dp[i-2][j+1]==i-2:
                        dp[i][j]=i
                        continue
                mx=dp[i-2][j+1]                
                for k in range(2,i,2):
                    if mx<dp[k][j]+dp[i-k][j+k]:
                        mx=dp[k][j]+dp[i-k][j+k]
                        if mx==i:break
            else :
                for k in range(1,i,2):
                    if mx<dp[k][j]+dp[i-k][j+k]:
                        mx=dp[k][j]+dp[i-k][j+k]                
            dp[i][j]=mx
    print(dp[n][0])        
    

                

while 1:
    n=int(input())
    if n==0 : break
    lst=tuple(map(int,input().split()))
    solve(n,lst)

Solution (Python):
def solve(n,w):
    dp=[[0]*(n+1) for _ in range(n+1)]
    for kukan in range(2,n+1):
        for l in range(0,n+1-kukan):
            r=l+kukan
            
            if (kukan-2)%2==0:
                if abs(w[l]-w[r-1])<=1 and dp[l+1][r-1]==r-l-2:
                    dp[l][r]=dp[l+1][r-1]+2
                    continue
            for i in range(l+1,r):
                if dp[l][r]<(dp[l][i]+dp[i][r]):
                    dp[l][r]=dp[l][i]+dp[i][r]
    return dp[0][n]
            

n=int(input())
while(n!=0):
    w=list(map(int,input().split()))
    print(solve(n,w))
    n=int(input())

Solution (Python):
import sys

while True:
    n=int(input())
    if n==0:
        break
    w = [int(x) for x in sys.stdin.readline().split()]

    dp=[[0]*n for i in range(n)] 

    for l in range(n-1):
        r=l+1
        if abs(w[l]-w[r])<2:
            dp[l][r]=2
        
    for i in range(2,n):
        if i%2==1:
            for l in range(n-i):
                r=l+i
                if dp[l+1][r-1]==r-l-1 and abs(w[l]-w[r])<2:
                    dp[l][r]=r-l+1
                else:
                    for lr in range(l+1,r):
                        if dp[l][r]< dp[l][lr]+dp[lr+1][r]:
                            dp[l][r]=dp[l][lr]+dp[lr+1][r]
        else:
            for l in range(n-i):
                r=l+i

                if dp[l][r]<dp[l+1][r]:
                    dp[l][r]=dp[l+1][r]
                if dp[l][r]<dp[l][r-1]:
                    dp[l][r]=dp[l][r-1]
    print(dp[0][n-1])

Solution (Python):
def main(n):
    a = list(map(int, input().split()))
    dp = [[0] * (n+1) for i in range(n)]
    
    for i in range(n - 1):
        if abs(a[i] - a[i + 1]) <= 1:
            dp[i][i + 2] = 2
            
    for i in range(2, n): 
        for l in range(n-i): 
            r = i+l+1 
            if abs(a[l] - a[r-1]) <= 1: 
                if dp[l+1][r-1] == r-l-2: 
                    dp[l][r] = r-l 
                    continue
            res = dp[l+1][r-1] 
            for li in range(l+1, r): 
                tmp = dp[l][li] + dp[li][r] 
                if res < tmp: 
                    res = tmp
            dp[l][r] = res
    print(dp[0][n]) 

if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Solution (Python):
def main(n):
    a = list(map(int, input().split()))
    dp = [[0] * n for i in range(n)]
    for i in range(n - 1):
        if abs(a[i] - a[i + 1]) <= 1:
            dp[i][i + 1] = 2
    for i in range(2, n):
        for l in range(n - i):
            r = i + l
            res = 0
            if abs(a[l] - a[r]) <= 1:
                if dp[l + 1][r - 1] == r - l - 1:
                    dp[l][r] = r - l + 1
                    continue
            res = dp[l + 1][r - 1]
            for li in range(l + 1, r):
                tmp = dp[l][li] + dp[li + 1][r]
                if res < tmp:
                    res = tmp
            dp[l][r] = res
    print(dp[0][n-1])
    def dfs(l, r):
        if l >= r: return 0
        if dp[l][r] != -1: return dp[l][r]
        if abs(a[l] - a[r]) <= 1:
            if dfs(l + 1, r - 1) == r - l - 1:
                dp[l][r] = r - l + 1
                return r - l + 1
        res = 0
        for li in range(l + 1, r):
            tmp = 0
            f = 0
            if dp[l][li] != -1:
                tmp += dp[l][li]
            else:
                tmp += dfs(l, li)
            if dp[li + 1][r] != -1:
                tmp += dp[li + 1][r]
            else:
                tmp += dfs(li + 1, r)
            if res < tmp:
                res = tmp
        dp[l][r] = res
        return res
    


if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Solution (Python):



import sys


def main():
    while True:
        N = int(input())
        if N == 0:
            break
        w = list(map(int, sys.stdin.readline().strip().split()))

        
        dp = [[0] * N for _ in range(N)]

        for i in range(N - 1):
            if abs(w[i] - w[i + 1]) <= 1:
                dp[i][i + 1] = 2

        
        for l in range(2, N):
            for i in range(N - l):
                j = i + l

                if l % 2 == 1:
                    if dp[i + 1][j - 1] == l - 1 and (abs(w[i] - w[j]) <= 1):
                        dp[i][j] = l + 1
                        continue

                for k in range(i, j):
                    if dp[i][j] < dp[i][k] + dp[k + 1][j]:
                        dp[i][j] = dp[i][k] + dp[k + 1][j]
                        if dp[i][j] == l:
                            break

        
        

        print(dp[0][-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def func():
    while True:
        N = int(input())
        if N == 0: break
        W = [int(i) for i in input().split()]
        
        dp = [[0]*(N+1) for j in range(N+1)]

        for s in range(2, N+1):
            for l in range(N-s+1):
                r = l + s
                if (s - 2) % 2 == 0:
                    if dp[l+1][r-1] == s-2 and abs(W[l] - W[r-1]) <= 1:
                        dp[l][r] = s
                        continue
                for i in range(l, r+1):
                    if dp[l][r] < dp[l][i] + dp[i][r]:
                        dp[l][r] = dp[l][i] + dp[i][r]

        print(dp[0][N])

if __name__ == "__main__":
    func()

Solution (Python):
import sys



def main():
  while True:
    n = int(input())
    if(n == 0):
      break
    w = list(map(int, input().split()))
    
    dp = [[0] * (n+1) for _ in range(n+1)]
    
    for gap in range(2,n+1):
      
      for l in range(n-gap+1):
        r = l+gap
        if(dp[l+1][r-1] == gap-2):
          if(abs(w[l]-w[r-1]) <= 1):
            dp[l][r] = gap
            continue
        for k in range(l, r):
          if(dp[l][r] < dp[l][k] + dp[k][r]):
            dp[l][r] = dp[l][k] + dp[k][r]
    print(dp[0][n])
    
    
if __name__ == '__main__':
  main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
  while True:
    n = int(input())
    if(n == 0):
      break
    w = list(map(int, input().split()))
    dp = [[0] * (n+1) for _ in range(n+2)]
    for gap in range(2,n+1):
      for l in range(n-gap+1):
        r = l+gap
        if(dp[l+1][r-1] == gap-2):
          if(abs(w[l]-w[r-1]) <= 1):
            dp[l][r] = gap
            continue
        for k in range(l, r):
          if(dp[l][r] < dp[l][k]+dp[k][r]):
            dp[l][r] = dp[l][k]+dp[k][r]
    print(dp[0][n])
    
if __name__ == '__main__':
  main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    while True:
        n = int(input())
        w = list(map(int, input().split()))
        if n==0:
            break
        else:
            dp = [[0]*(n+1) for _ in range(n+2)]
            
            for i in range(2, n+1):
                for l in range(n-i+1):
                    r = l+i
                    if dp[l+1][r-1] == i-2:
                        if abs(w[l]-w[r-1])<=1:
                            dp[l][r] = i
                        else:
                            dp[l][r] = i-2
                    for j in range(l, r):
                        if dp[l][j] + dp[j][r] > dp[l][r]:
                            dp[l][r] = dp[l][j] + dp[j][r]

            print(dp[0][-1])        

if __name__ == '__main__':
    resolve()

Solution (Python):



def resolve():
    while True:
        n = int(input())

        if n == 0:
            exit()
        w = list(map(int, input().split()))
        
        dp = [[0]*(n+1) for _ in range(n+2)]
        for gap in range(2,n+1):
            for l in range(n-gap+1):
                r = l + gap
                if dp[l+1][r-1] == gap-2:
                    if abs(w[l] - w[r-1]) <= 1:
                        dp[l][r] = gap
                    else:
                        dp[l][r] = gap - 2
                for k in range(l,r):
                    if dp[l][k] + dp[k][r] > dp[l][r]:
                            dp[l][r] = dp[l][k] + dp[k][r]
                    
        
        
        print(dp[0][-1])
if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
  while True:
    n = int(input())
    if(n == 0):
      break
    w = list(map(int, input().split()))
    dp = [[0] * (n+1) for _ in range(n+2)]
    for gap in range(2,n+1):
      for l in range(n-gap+1):
        r = l+gap
        if(dp[l+1][r-1] == gap-2):
          if(abs(w[l]-w[r-1]) <= 1):
            dp[l][r] = gap
            continue
        for k in range(l, r):
          if(dp[l][r] < dp[l][k]+dp[k][r]):
            dp[l][r] = dp[l][k]+dp[k][r]
    print(dp[0][n])
    
if __name__ == '__main__':
  main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    while True:
        n = int(input())
        w = list(map(int, input().split()))
        if n==0:
            break
        else:
            dp = [[0]*(n+1) for _ in range(n+2)]
            
            for i in range(2, n+1):
                for l in range(n-i+1):
                    r = l+i
                    if dp[l+1][r-1] == i-2:
                        if abs(w[l]-w[r-1])<=1:
                            dp[l][r] = i
                        else:
                            dp[l][r] = i-2
                    for j in range(l, r):
                        if dp[l][j] + dp[j][r] > dp[l][r]:
                            dp[l][r] = dp[l][j] + dp[j][r]

            print(dp[0][-1])        

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def ti(): return tuple(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]






def solve(N):
    A = ti()
    dp = dp2(0, N, N)

    for i in range(N-1):
        if abs(A[i]-A[i+1]) < 2:
            dp[i][i+1] = 2
    
    for h in range(2, N): 
        for i in range(N):
            if i+h >= N:
                break
            j = i+h
            
            if h % 2:
                if abs(A[i]-A[j]) < 2 and dp[i+1][j-1] == h-1:
                    dp[i][j] = h + 1
                    continue
                else:
                    dp[i][j] = max(tuple(dp[i][k]+dp[k+1][j] for k in range(i, j)))
            
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        else:
            continue

    print(dp[0][N-1])

while True:
    N = ii()
    if N == 0:
        exit()
    solve(N)

Solution (Python):
while True:
    n=int(input())
    if(n==0):
        exit()
    w=list(map(int,input().split()))
    c=[[False]*n for _ in range(n)]
    dp=[0]*(n+1)
    for i in range(n-1):
        if abs(w[i]-w[i+1])<=1:
            c[i][i+1]=True
    for i in range(3,n,2):
        for l in range(n-i):
            r=l+i
            for k in range(l+1,r):
                if not c[l][r] and c[l][k] and c[k+1][r]:
                    c[l][r]=True
                    break
            if (not c[l][r]) and c[l+1][r-1] and abs(w[l]-w[r])<=1:
                c[l][r]=True
    for i in range(n):
        for j in range(n):
            if c[j][i]:
                dp[i]=max(dp[i],dp[j-1]+i-j+1)
        dp[i]=max(dp[i],dp[i-1])
    print(dp[n-1])

Solution (Python):

while True:
    n=int(input())
    if n== 0:
        break
    
    A = list(map(int, input().split()))
    c = [[0]*n for _ in range(n)]
    for i in range(n):
        c[i][i] = 0
        
    for i in range(1, n):
        if i%2==0:
            continue
        for j in range(n-i):
            if i==1 and abs(A[j] - A[j+i])<=1:
                    c[j][j+i] = 1 
            else:
                for k in range(j+1, j+i-1):
                    
                    if c[j][k] and c[k+1][j+i]:
                        c[j][j+i] = 1
                        break
                if c[j+1][j+i-1] and abs(A[j] - A[j+i])<=1:
                    c[j][j+i] = 1
    
    dp = [[0]*n for _ in range(n)]
    
    for i in range(1):
        for j in range(i, n):
            if c[i][j]:
                dp[i][j] = j-i+1
            else:
                for k in range(i, j):
                    if c[k+1][j]:
                        dp[i][j] = max(dp[i][j], dp[i][k] + j-k)
                if j>i:
                    dp[i][j] = max(dp[i][j], dp[i][j-1])
    
    print(dp[0][n-1])

Solution (Python):

import sys
input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 8)
def solve():
    n = int(input())
    while n != 0:
        w = tuple(map(int, input().split()))
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if (j - i + 1) % 2 == 0:
                    if dp[i + 1][j - 1] == j - i - 1 and abs(w[i] - w[j]) <= 1:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                    else:
                        p = tuple(dp[i][k] + dp[k + 1][j] for k in range(i, j + 1))
                        dp[i][j] = max(p)
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
        print(dp[0][n - 1])
        n = int(input())


if __name__ == "__main__":
    solve()

Solution (Python):

def main():
    while True:
        N = int(input())
        if N == 0:
            exit()
        A = list(map(int,input().split()))
        can_drop = [[False] * N for _ in range(N)]
        
        d = [0] * (N+1)

        
        for i in range(N-1):
            if abs(A[i] - A[i+1]) <= 1:
                can_drop[i][i+1] = True

        
        for i in range(3, N, 2):
            
            for j in range(N-i):
                
                last = j + i
                for k in range(j+1, j+i):
                    
                    if not can_drop[j][last] and can_drop[j][k] and can_drop[k+1][last]:
                        can_drop[j][last] = True
                        break
                
                if not can_drop[j][last] and can_drop[j+1][last-1] and abs(A[j] - A[last]) <= 1:
                    can_drop[j][last] = True

        
        for i in range(N):
            for j in range(N):
                if can_drop[j][i]:
                    d[i] = max(d[i], d[j-1] + i - j + 1)
        
            d[i] = max(d[i], d[i - 1])
        print(d[N-1])        

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
while True:
    l1 = list(map(int,input().split()))
    c = [[False] * n for i in range(n)]
    d = [0] * (n + 1)
    for i in range(n - 1):
        if abs(l1[i + 1] - l1[i]) <= 1:
            c[i][i + 1] = True
            
    for i in range(3, n, 2):
        for j in range(n - i):
            for k in range(j + 1, j + i):
                if c[j][j + i] == False and c[j][k] and c[k + 1][j + i]:
                    c[j][j + i] = True
                    break
            if c[j][j + i] == False and abs(l1[j] - l1[j + i]) <= 1 and c[j + 1][j + i - 1]:
                c[j][j + i] = True
                
    for i in range(n):
        for j in range(i):
            if c[j][i]:
                d[i] = max(d[i], d[j - 1] + i - j + 1)
        d[i] = max(d[i], d[i - 1])
        
    print(d[n - 1])
    
    n = int(input())
    if n == 0:
        break