You are given an array $a_1, a_2, \dots, a_n$. You can perform the following operation any number of times:  Choose a pair of two neighboring equal elements $a_i = a_{i + 1}$ (if there is at least one such pair).  Replace them by one element with value $a_i + 1$. 

After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array $a$ you can get?


-----Input-----

The first line contains the single integer $n$ ($1 \le n \le 500$) — the initial length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$) — the initial array $a$.


-----Output-----

Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.


-----Examples-----
Input
5
4 3 2 2 3

Output
2

Input
7
3 3 4 4 4 3 3

Output
2

Input
3
1 3 5

Output
3

Input
1
1000

Output
1



-----Note-----

In the first test, this is one of the optimal sequences of operations: $4$ $3$ $2$ $2$ $3$ $\rightarrow$ $4$ $3$ $3$ $3$ $\rightarrow$ $4$ $4$ $3$ $\rightarrow$ $5$ $3$.

In the second test, this is one of the optimal sequences of operations: $3$ $3$ $4$ $4$ $4$ $3$ $3$ $\rightarrow$ $4$ $4$ $4$ $4$ $3$ $3$ $\rightarrow$ $4$ $4$ $4$ $4$ $4$ $\rightarrow$ $5$ $4$ $4$ $4$ $\rightarrow$ $5$ $5$ $4$ $\rightarrow$ $6$ $4$.

In the third and fourth tests, you can't perform the operation at all.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))

dp = [[False] * (n + 1) for i in range(n + 1)]

def solve(l, r):
    if dp[l][r]:
        return dp[l][r]
    if r - l == 1:
        dp[l][r] = (a[l], 1)
        return dp[l][r]
    tmp = 10 ** 9
    for i in range(l + 1, r):
        if solve(l, i)[0] == -1 or solve(i, r)[0] == -1:
            tmp = min(tmp, dp[l][i][1] + dp[i][r][1])
        elif solve(l, i) == solve(i, r):
            tmp = solve(l, i)[0] + 1
            dp[l][r] = (tmp, 1)
            return dp[l][r]
        else:
            tmp = min(tmp, 2)
    dp[l][r] = (-1, tmp)
    return dp[l][r]

solve(0, n)
print(dp[0][n][1])

rr = lambda: input().rstrip()
rri = lambda: int(rr())
rrm = lambda: list(map(int, rr().split()))

from functools import lru_cache;memo=lru_cache(None)
from sys import setrecursionlimit as srl;srl(10**5)

def solve(N, A):
    @memo
    def dp(i, j, left=0):
        if i == j:
            if left == 0:
                return 1
            if A[i] == left:
                return 1
            return 2
        if i > j:
            return 0 if left == 0 else 1
        # Try to greedy run up until left
        ans = 1 + dp(i+1, j, A[i])
        if left >= 1:
            stack = []
            for k in range(i, j+1):
                stack.append(A[k])
                
                while len(stack) >= 2 and stack[-1] == stack[-2]:
                    stack.pop()
                    stack[-1] += 1
                if len(stack) == 1 and left == stack[-1]:
                    cand = dp(k+1, j, left+1)
                    if cand < ans:
                        ans = cand
        return ans

    return dp(1, N-1, A[0])

#print(solve(2,[2,2]))
#print(solve(3,[3,2,2]))
#print(solve(4,[3,2,2,3]))
#print(solve(5,[4,3,2,2,3]))    
#print(solve(4,[4,3,2,2]))
#import random;random.seed(0);ri=random.randint
#print(solve(500, [ri(1,5) for _ in range(500)]))
print(solve(rri(), rrm()))


def f():
    n = int(input())
    A = [int(s) for s in input().split()]
    memo = [[None for j in range(n+1)] for i in range(n+1)]
    for i in range(n):
        memo[i][i] = [A[i],A[i],1]  # startEle, endEle, minlen
    for l in range(2,n+1):
        for left in range(0,n-l+1):
            right = left + l - 1  # [left, right]
            minLen = l
            shortestMid = right
            for mid in range(left+1,right+1):
                pre = memo[left][mid-1]
                post = memo[mid][right]
                combLen = pre[2] + post[2]
                if pre[1]==post[0]:
                    combLen -= 1
                if combLen < minLen:
                    minLen = combLen
                    shortestMid = mid
            pre = memo[left][shortestMid - 1]
            post = memo[shortestMid][right]
            startEle = pre[0]
            endEle = post[1]
            if pre[2] == 1:
                if pre[0] == post[0]:
                    startEle = pre[0] + 1
            if post[2] == 1:
                if pre[1] == post[0]:
                    endEle = post[0] + 1
            memo[left][right] = [startEle, endEle, minLen]
    # print(memo[0][n-1])
    print(memo[0][n-1][2])


f()