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.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Greedy algorithms


Solutions:
n = int(input())
arr = list(map(int, input().split()))
tracker = [[-1] * (n + 1) for _ in range(2024)]
d = [[] for _ in range(n)]
for (j, v) in enumerate(arr):
	tracker[v][j] = j
	d[j].append(j)
for v in range(1, 2024):
	for i in range(n):
		j = tracker[v][i]
		h = tracker[v][j + 1] if j != -1 else -1
		if j != -1 and h != -1:
			tracker[v + 1][i] = h
			d[i].append(h)
a = [_ for _ in range(1, n + 1)]
for s in range(n):
	for tracker in d[s]:
		a[tracker] = min(a[tracker], a[s - 1] + 1 if s > 0 else 1)
print(a[n - 1])


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 9
dp = [[INF] * (n + 1) for i in range(n + 1)]
val = [[-1] * (n + 1) for i in range(n + 1)]
for i in range(n):
	dp[i][i + 1] = 1
	val[i][i + 1] = a[i]
for l in range(2, n + 1):
	for i in range(n - l + 1):
		j = i + l
		for k in range(i + 1, j):
			if dp[i][k] == dp[k][j] == 1 and val[i][k] == val[k][j]:
				dp[i][j] = 1
				val[i][j] = val[i][k] + 1
			else:
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
print(dp[0][n])


import sys
readline = sys.stdin.buffer.readline
N = int(readline())
A = list(map(int, readline().split()))
dp = [[0] * N for _ in range(N)]
for j in range(N):
	dp[j][0] = A[j]
for l in range(1, N):
	for j in range(l, N):
		for k in range(j - l, j):
			if dp[k][k - j + l] == dp[j][j - k - 1] > 0:
				dp[j][l] = 1 + dp[j][j - k - 1]
				break
dp = [None] + dp
Dp = [0] * (N + 1)
for j in range(1, N + 1):
	res = N
	for l in range(j):
		if dp[j][l]:
			res = min(res, 1 + Dp[j - l - 1])
	Dp[j] = res
print(Dp[N])


n = int(input())
A = list(map(int, input().split()))
INF = 10 ** 3
dp = [[INF] * (n + 1) for _ in range(n + 1)]
val = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
	dp[i][i + 1] = 1
for i in range(n):
	val[i][i + 1] = A[i]
for d in range(2, n + 1):
	for i in range(n + 1 - d):
		j = i + d
		for k in range(i + 1, j):
			if dp[i][k] == 1 and dp[k][j] == 1 and (val[i][k] == val[k][j]):
				dp[i][j] = min(dp[i][j], 1)
				val[i][j] = val[i][k] + 1
			else:
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
print(dp[0][n])


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def IF():
	return float(input())

def S():
	return input().rstrip()

def LS():
	return S().split()

def IR(n):
	res = [None] * n
	for i in range(n):
		res[i] = II()
	return res

def LIR(n):
	res = [None] * n
	for i in range(n):
		res[i] = LI()
	return res

def FR(n):
	res = [None] * n
	for i in range(n):
		res[i] = IF()
	return res

def LIR(n):
	res = [None] * n
	for i in range(n):
		res[i] = IF()
	return res

def LIR_(n):
	res = [None] * n
	for i in range(n):
		res[i] = LI_()
	return res

def SR(n):
	res = [None] * n
	for i in range(n):
		res[i] = S()
	return res

def LSR(n):
	res = [None] * n
	for i in range(n):
		res[i] = LS()
	return res
mod = 1000000007
inf = float('INF')

def solve():
	n = II()
	a = LI()
	dp = [[None for i in range(n + 1)] for i in range(n + 1)]
	for i in range(n):
		dp[i][i + 1] = [a[i], a[i], 1]
		dp[i + 1][i] = [a[i], a[i], 1]
	for i in range(2, n + 1):
		for l in range(n - i + 1):
			tmp = [-inf, inf, inf]
			r = l + i
			dpl = dp[l]
			dpr = dp[r]
			for m in range(l + 1, r):
				lm = dpl[m]
				mr = dpr[m]
				lr = lm[2] + mr[2] - (lm[1] == mr[0])
				if lr < tmp[2]:
					tmp[2] = lr
					if lm[1] == mr[0]:
						if lm[2] == 1:
							tmp[0] = lm[0] + 1
						else:
							tmp[0] = lm[0]
						if mr[2] == 1:
							tmp[1] = mr[1] + 1
						else:
							tmp[1] = mr[1]
					else:
						tmp[0] = lm[0]
						tmp[1] = mr[1]
			dp[l][r] = tmp
			dp[r][l] = tmp
	print(dp[0][n][2])
	return
solve()


import io
import os
import sys
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(10 ** 5)

def solve(N, A):
	valToLeftRight = defaultdict(lambda : defaultdict(set))
	valToRightLeft = defaultdict(lambda : defaultdict(set))
	for (i, x) in enumerate(A):
		valToLeftRight[x][i].add(i)
		valToRightLeft[x][i].add(i)
	maxVal = 1000 + 10
	for val in range(maxVal):
		for (l, rights) in valToLeftRight[val - 1].items():
			for r in rights:
				l2 = r + 1
				if l2 in valToLeftRight[val - 1]:
					for r2 in valToLeftRight[val - 1][l2]:
						assert l <= r
						assert r + 1 == l2
						assert l2 <= r2
						valToLeftRight[val][l].add(r2)
						valToRightLeft[val][r2].add(l)
				r2 = l - 1
				if r2 in valToRightLeft[val - 1]:
					for l2 in valToRightLeft[val - 1][r2]:
						assert l2 <= r2
						assert r2 == l - 1
						assert l <= r
						valToLeftRight[val][l2].add(r)
						valToRightLeft[val][r].add(l2)
	intervals = defaultdict(list)
	for val in range(maxVal):
		for (l, rights) in valToLeftRight[val].items():
			for r in rights:
				intervals[l].append(r)

	@lru_cache(maxsize=None)
	def getBest(left):
		if left == N:
			return 0
		best = float('inf')
		for right in intervals[left]:
			best = min(best, 1 + getBest(right + 1))
		return best
	return getBest(0)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = solve(N, A)
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
DP = [[-1] * (n + 1) for i in range(n + 1)]
for i in range(n):
	DP[i][i] = A[i]
for mid in range(1, n):
	for i in range(n):
		j = i + mid
		if j == n:
			break
		for k in range(i, j + 1):
			if DP[i][k] == DP[k + 1][j] and DP[i][k] != -1:
				DP[i][j] = DP[i][k] + 1
ANS = [2000] * (n + 1)
ANS.append(0)
for i in range(n):
	ANS[i] = min(ANS[i], ANS[i - 1] + 1)
	for j in range(i, n):
		if DP[i][j] != -1:
			ANS[j] = min(ANS[j], ANS[i - 1] + 1)
print(ANS[n - 1])


n = int(input())
b = [int(_) for _ in input().split()]
e = [[-1] * (n + 1) for _ in range(2024)]
d = [[] for _ in range(n)]
for (j, v) in enumerate(b):
	e[v][j] = j
	d[j].append(j)
for v in range(1, 2024):
	for i in range(n):
		j = e[v][i]
		h = e[v][j + 1] if j != -1 else -1
		if j != -1 and h != -1:
			e[v + 1][i] = h
			d[i].append(h)
a = [_ for _ in range(1, n + 1)]
for s in range(n):
	for e in d[s]:
		a[e] = min(a[e], a[s - 1] + 1 if s > 0 else 1)
print(a[n - 1])


n = int(input())
a = list(map(int, input().split()))
dp = [[505] * n for _ in range(n)]
Max = [[0] * n for _ in range(n)]
for i in range(n):
	dp[i][i] = 1
	Max[i][i] = a[i]
for len in range(1, n + 1):
	for i in range(n - len + 1):
		j = i + len - 1
		for k in range(i, j):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
			if dp[i][k] == 1 and dp[k + 1][j] == 1 and (Max[i][k] == Max[k + 1][j]):
				dp[i][j] = 1
				Max[i][j] = Max[i][k] + 1
print(dp[0][n - 1])


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
INF = float('inf')
mod = int(1000000000.0) + 7

def cal(l, r):
	if l == r:
		dp1[l][r] = 1
		dp2[l][r] = a[l]
	if dp1[l][r]:
		return dp1[l][r]
	for i in range(l, r):
		if cal(l, i) == 1 and cal(i + 1, r) == 1 and (dp2[l][i] == dp2[i + 1][r]):
			dp1[l][r] = 1
			dp2[l][r] = dp2[l][i] + 1
	if not dp2[l][r]:
		dp1[l][r] = 2
	return dp1[l][r]

def cal2(l, r):
	if dp1[l][r] == 1:
		dp3[l][r] = 1
		return 1
	elif dp3[l][r]:
		return dp3[l][r]
	ans = INF
	for i in range(l, r):
		ans = min(cal2(l, i) + cal2(i + 1, r), ans)
	dp3[l][r] = ans
	return ans
n = int(data())
a = mdata()
ans = [n]
dp1 = [[0] * n for i in range(n)]
dp2 = [[0] * n for i in range(n)]
dp3 = [[0] * n for i in range(n)]
cal(0, n - 1)
cal2(0, n - 1)
out(dp3[0][n - 1])


n = int(input())
b = list(map(int, input().split(' ')))
e = [[-1] * (n + 1) for _ in range(2048)]
d = [[] for _ in range(n)]
for (i, v) in enumerate(b):
	e[v][i] = i
	d[i].append(i)
for v in range(1, 2048):
	for i in range(n):
		j = e[v][i]
		if j != -1:
			h = e[v][j + 1]
		else:
			h = -1
		if j != -1 and h != -1:
			e[v + 1][i] = h
			d[i].append(h)
a = [_ for _ in range(1, n + 1)]
for s in range(n):
	for e in d[s]:
		if s > 0:
			temp = a[s - 1] + 1
		else:
			temp = 1
		a[e] = min(a[e], temp)
print(a[n - 1])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[False] * (n + 2) for i in range(n + 2)]
	dp2 = [[600] * (n + 2) for i in range(n + 2)]
	for i in range(n):
		dp[i][i] = a[i]
		dp2[i][i] = 1
	for diff in range(1, n):
		for i in range(n - diff):
			for j in range(i, i + diff):
				if dp[i][j] == dp[j + 1][i + diff] and dp[i][j]:
					dp[i][i + diff] = dp[i][j] + 1
					dp2[i][i + diff] = 1
				dp2[i][i + diff] = min(dp2[i][i + diff], dp2[i][j] + dp2[j + 1][i + diff])
			if not dp2[i][i + diff]:
				dp2[i][i + diff] = min(dp2[i + 1][i + diff] + 1, dp2[i][i + diff - 1] + 1)
	print(dp2[0][n - 1])


N = int(input())
X = list(map(int, input().split()))
from collections import defaultdict
dp1 = defaultdict(lambda : -1)
M = 1001

def ec(i, j):
	return i * M + j
for i in range(N):
	dp1[ec(i, i + 1)] = X[i]
for i in range(2, N + 1):
	for j in range(N - i + 1):
		for k in range(1, i):
			(u, v) = (dp1[ec(j, j + k)], dp1[ec(j + k, j + i)])
			if u != -1 and v != -1 and (u == v):
				dp1[ec(j, j + i)] = u + 1
				break
dp2 = [0] * (N + 1)
for i in range(N):
	dp2[i + 1] = dp2[i] + 1
	for j in range(i + 1):
		if dp1[ec(j, i + 1)] == -1:
			continue
		dp2[i + 1] = min(dp2[i + 1], dp2[j] + 1)
print(dp2[-1])


import sys
input = lambda : sys.stdin.readline().rstrip()
import copy
n = int(input())
A = [int(i) for i in input().split()]
inf = float('inf')
DP = [[inf] * (n + 1) for _ in range(n + 1)]
for j in range(1, n + 1):
	for i in range(n):
		if i + j > n:
			continue
		elif j == 1:
			DP[i][i + 1] = A[i]
		else:
			for k in range(i + 1, i + j):
				if DP[i][k] < 10000 and DP[k][i + j] < 10000:
					if DP[i][k] == DP[k][i + j]:
						DP[i][i + j] = DP[i][k] + 1
					else:
						DP[i][i + j] = 20000
				elif DP[i][k] < 10000:
					DP[i][i + j] = min(DP[i][i + j], 10000 + DP[k][i + j])
				elif DP[k][i + j] < 10000:
					DP[i][i + j] = min(DP[i][i + j], DP[i][k] + 10000)
				else:
					DP[i][i + j] = min(DP[i][i + j], DP[i][k] + DP[k][i + j])
print(DP[0][n] // 10000 if DP[0][n] >= 10000 else 1)


N = int(input())
X = list(map(int, input().split()))
from collections import defaultdict
dp = defaultdict(lambda : -1)
M = 1000001
for i in range(N):
	dp[i + M] = X[i]
for i in range(2, N + 1):
	for j in range(N - i + 1):
		for k in range(1, i):
			(u, v) = (dp[j + M * k], dp[j + k + M * (i - k)])
			if u == -1 or v == -1 or u != v:
				continue
			dp[j + M * i] = u + 1
			break
dp2 = [0] * (N + 1)
for i in range(N):
	dp2[i + 1] = dp2[i] + 1
	for j in range(i + 1):
		if dp[j + (i + 1 - j) * M] == -1:
			continue
		dp2[i + 1] = min(dp2[i + 1], dp2[j] + 1)
print(dp2[-1])


N = int(input())
L = list(map(int, input().split()))
DP = [[-1] * N for i in range(N)]
for d in range(N):
	for s in range(N - d):
		e = s + d
		if s == e:
			DP[s][e] = L[s]
			continue
		for m in range(s, e):
			l = DP[s][m]
			r = DP[m + 1][e]
			if l == r and l != -1:
				DP[s][e] = max(DP[s][e], l + 1)
DP2 = [i + 1 for i in range(N)]
for i in range(N):
	if DP[0][i] != -1:
		DP2[i] = 1
		continue
	for j in range(i):
		if DP[j + 1][i] != -1:
			DP2[i] = min(DP2[i], DP2[j] + 1)
print(DP2[N - 1])


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True and False
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)

def dp(l, r):
	if dpa[l][r] >= 0:
		return dpa[l][r]
	elif l == r:
		dpa[l][r] = a[l]
	else:
		dpa[l][r] = 0
		for j in range(l, r):
			x = dp(l, j)
			y = dp(j + 1, r)
			if 0 < x == y:
				dpa[l][r] = x + 1
	return dpa[l][r]
n = inn()
a = inl()
dpa = [[-1] * (n + 1) for i in range(n + 1)]
dp2 = [BIG] * (n + 1)
dp2[0] = 1
for i in range(n):
	if dp(0, i) > 0:
		dp2[i] = 1
	else:
		mn = i + 1
		for j in range(i):
			x = dp(j + 1, i)
			if 0 < x:
				mn = min(mn, dp2[j] + 1)
		dp2[i] = mn
for i in range(n):
	ddprint(dpa[i])
ddprint(dp2)
print(dp2[n - 1])


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
dp = [[1000] * (n + 1) for i in range(n + 1)]
val = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	dp[i][i + 1] = 1
	val[i][i + 1] = a[i]
for p in range(2, n + 1):
	for i in range(n - p + 1):
		j = i + p
		for k in range(i + 1, j):
			if dp[i][k] == dp[k][j] == 1 and val[i][k] == val[k][j]:
				dp[i][j] = 1
				val[i][j] = val[i][k] + 1
			else:
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
print(dp[0][n])


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
		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(rri(), rrm()))


n = int(input())
a = list(map(int, input().split()))
grip = [[-1] * (n - i) for i in range(n)]
grip[0] = a.copy()
for level in range(1, n):
	for left in range(n - level):
		for split in range(level):
			pl = grip[level - split - 1][left]
			pr = grip[split][left + level - split]
			if pl == pr != -1:
				grip[level][left] = pl + 1
pref = [0] * (n + 1)
for p in range(1, n + 1):
	x = n
	for j in range(p):
		l = pref[j]
		r = grip[p - j - 1][j]
		if r == -1:
			r = p - j
		else:
			r = 1
		x = min(x, l + r)
	pref[p] = x
print(pref[-1])


import os, sys
from io import BytesIO, IOBase
from math import inf

def main():
	n = int(input())
	a = [0] + list(map(int, input().split()))
	dp = [[[-1, 0] for _ in range(n + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		(dp[i][i][0], dp[i][i][1]) = (a[i], 1)
	for i in range(n - 1, 0, -1):
		for j in range(i + 1, n + 1):
			for k in range(j - i):
				(a, b) = (dp[i][i + k], dp[i + k + 1][j])
				if a[1] and b[1] and (a[0] == b[0]):
					(dp[i][j][0], dp[i][j][1]) = (a[0] + 1, 1)
					break
	val = [0, 0] + [inf] * n
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if dp[i][j][1]:
				val[j + 1] = min(val[j + 1], val[i] + 1)
	print(val[-1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
dp = []
a = []

def calcdp(l, r):
	global dp, a
	if l + 1 == r:
		dp[l][r] = a[l]
		return dp[l][r]
	if dp[l][r] != 0:
		return dp[l][r]
	dp[l][r] = -1
	for k in range(l + 1, r):
		la = calcdp(l, k)
		ra = calcdp(k, r)
		if la > 0 and la == ra:
			dp[l][r] = la + 1
	return dp[l][r]

def solve(n):
	dp2 = [float('inf')] * (n + 1)
	dp2[0] = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			if calcdp(i, j) > 0:
				dp2[j] = min(dp2[j], dp2[i] + 1)
	return dp2[n]

def ip():
	global dp, a
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	a.append(0)
	dp = []
	ll = [0] * (n + 1)
	for _ in range(n + 1):
		dp.append(list(ll))
	print(solve(n))
ip()


N = int(input())
arr = list(map(int, input().split()))
dp = [[-1 for x in range(N)] for y in range(N)]
for size in range(1, N + 1):
	for i in range(N - size + 1):
		j = i + size - 1
		if i == j:
			dp[i][j] = arr[i]
		else:
			for k in range(i, j):
				if dp[i][k] != -1 and dp[i][k] == dp[k + 1][j]:
					dp[i][j] = dp[i][k] + 1
dp2 = [x + 1 for x in range(N)]
for i in range(N):
	for k in range(i + 1):
		if dp[k][i] != -1:
			if k == 0:
				dp2[i] = 1
			else:
				dp2[i] = min(dp2[i], dp2[k - 1] + 1)
print(dp2[N - 1])


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])


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
dp = [[-1] * (N + 1) for _ in range(N + 1)]
for l in range(N):
	dp[l][l + 1] = A[l]
for d in range(2, N + 1):
	for l in range(N - d + 1):
		for t in range(1, d):
			if dp[l][l + t] == dp[l + t][l + d] and dp[l][l + t] != -1:
				dp[l][l + d] = dp[l][l + t] + 1
				break
dp2 = [i for i in range(N + 1)]
for r in range(1, N + 1):
	if dp[0][r] != -1:
		dp2[r] = 1
for l in range(N):
	for r in range(l + 2, N + 1):
		if dp[l + 1][r] != -1:
			dp2[r] = min(dp2[l + 1] + 1, dp2[r])
		else:
			dp2[r] = min(dp2[l + 1] + (r - l - 1), dp2[r])
print(dp2[N])


from collections import Counter
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
n = iinput()
a = rlinput()
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	dp[i][i] = a[i]
for l in range(n - 2, -1, -1):
	for r in range(l + 1, n):
		for k in range(l, r):
			if dp[l][k] == dp[k + 1][r] and dp[l][k] != 0:
				dp[l][r] = dp[l][k] + 1
squeeze = [float('inf')] * (n + 1)
squeeze[0] = 0
for i in range(1, n + 1):
	for j in range(i):
		if dp[j][i - 1] != 0:
			squeeze[i] = min(squeeze[i], squeeze[j] + 1)
print(squeeze[n])


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	if n == 1:
		return 0
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [digit[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [digit[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matridigit[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matridigit[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matridigit[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matridigit[i][j] + other._matridigit[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matridigit[i][j] - other._matridigit[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matridigit[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matridigit[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matridigit[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)
from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
N = int(input())
A = li()
dp = [[False for r in range(N)] for l in range(N)]
for l in range(N):
	tmp = [A[l]]
	dp[l][l] = True
	for r in range(l + 1, N):
		val = A[r]
		while tmp and tmp[-1] == val:
			val = tmp[-1] + 1
			tmp.pop()
		tmp.append(val)
		if len(tmp) == 1:
			dp[l][r] = True
res = [i for i in range(N + 1)]
for r in range(1, N + 1):
	for l in range(1, r + 1):
		if dp[l - 1][r - 1]:
			res[r] = min(res[r], 1 + res[l - 1])
print(res[N])


from sys import stdin, gettrace
if not gettrace():

	def input():
		return next(stdin)[:-1]
INF = 10000

def main():
	n = int(input())
	aa = [int(a) for a in input().split()]
	dp = [[0] * (n + 1) for _ in range(n)]

	def calc_dp(i, j):
		if i + 1 == j:
			dp[i][j] = aa[i]
		if dp[i][j] != 0:
			return dp[i][j]
		dp[i][j] = -1
		for k in range(i + 1, j):
			lf = calc_dp(i, k)
			rg = calc_dp(k, j)
			if lf > 0 and lf == rg:
				dp[i][j] = lf + 1
				break
		return dp[i][j]
	dp2 = list(range(0, n + 1))
	for i in range(n):
		for j in range(i + 1, n + 1):
			if calc_dp(i, j) > 0:
				dp2[j] = min(dp2[j], dp2[i] + 1)
	print(dp2[n])
main()


n = int(input())
a = list(map(int, input().split(' ')))
new_a = [[0] * 600 for i in range(600)]
dp = [[2147483647] * 600 for i in range(600)]
for i in range(n):
	new_a[i + 1][i + 1] = a[i]
	dp[i + 1][i + 1] = 1
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		dp[i][j] = j - i + 1
for llen in range(2, n + 1):
	for left in range(1, n - llen + 2):
		right = left + llen - 1
		for middle in range(left, right):
			dp[left][right] = min(dp[left][right], dp[left][middle] + dp[middle + 1][right])
			if dp[left][middle] == 1 and dp[middle + 1][right] == 1 and (new_a[left][middle] == new_a[middle + 1][right]):
				dp[left][right] = 1
				new_a[left][right] = new_a[left][middle] + 1
print(dp[1][n])


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 998244353

def solve():
	N = getInt()
	A = getInts()
	dp = [[-1 for j in range(N)] for i in range(N)]
	for i in range(N):
		dp[i][i] = A[i]
	for X in range(2, N + 1):
		for i in range(N - X + 1):
			j = i + X - 1
			for k in range(i, j):
				if dp[i][k] == dp[k + 1][j] and dp[i][k] != -1:
					dp[i][j] = dp[i][k] + 1
					break
	ans = [10 ** 9 + 1] * (N + 1)
	ans[0] = 0
	for i in range(1, N + 1):
		for k in range(1, i + 1):
			if dp[k - 1][i - 1] != -1:
				ans[i] = min(ans[i], ans[k - 1] + 1)
	return ans[N]
print(solve())


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations, permutations
from bisect import *
from fractions import Fraction
from heapq import *
from random import randint

def main():
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dp[i][i] = a[i]
	for i in range(n - 2, -1, -1):
		for j in range(i + 1, n, 1):
			for k in range(i, j, 1):
				if dp[i][k] and dp[i][k] == dp[k + 1][j]:
					dp[i][j] = dp[i][k] + 1
	b = [10 ** 10] * (n + 1)
	b[0] = 0
	for i in range(1, n + 1):
		for j in range(i):
			if dp[j][i - 1]:
				b[i] = min(b[i], b[j] + 1)
	print(b[n])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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]
	for l in range(2, n + 1):
		for left in range(0, n - l + 1):
			right = left + l - 1
			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][2])
f()


import sys
import bisect
import heapq
from collections import defaultdict as dd
from collections import deque
from collections import Counter as c
from itertools import combinations as comb
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(var)

def l():
	return list(map(int, data().split()))

def sl():
	return list(map(str, data().split()))

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [[val for i in range(n)] for j in range(m)]
n = int(data())
arr = l()
dp = [[0 for j in range(500)] for i in range(500)]
dp2 = [0 for i in range(501)]
for i in range(n):
	dp[i][i] = arr[i]
i = n - 2
while ~i:
	j = i + 1
	while j < n:
		dp[i][j] = -1
		for k in range(i, j):
			if (~dp[i][k] and dp[i][k]) == dp[k + 1][j]:
				dp[i][j] = dp[i][k] + 1
		j += 1
	i -= 1
for i in range(1, n + 1):
	dp2[i] = pow(10, 9)
	for j in range(i):
		if ~dp[j][i - 1]:
			dp2[i] = min(dp2[i], dp2[j] + 1)
out(str(dp2[n]))


from heapq import *
import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	inf = 10 ** 9
	n = II()
	aa = LI()
	dp1 = [[-1] * (n + 1) for _ in range(n)]
	to = [[i + 1] for i in range(n)]
	for i in range(n):
		dp1[i][i + 1] = aa[i]
	for w in range(2, n + 1):
		for l in range(n - w + 1):
			r = l + w
			for m in range(l + 1, r):
				if dp1[l][m] != -1 and dp1[l][m] == dp1[m][r]:
					dp1[l][r] = dp1[l][m] + 1
					to[l].append(r)
	hp = []
	heappush(hp, (0, 0))
	dist = [-1] * (n + 1)
	while hp:
		(d, i) = heappop(hp)
		if i == n:
			print(d)
			break
		if dist[i] != -1:
			continue
		dist[i] = d
		for j in to[i]:
			if dist[j] != -1:
				continue
			heappush(hp, (d + 1, j))
main()


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	n = int(input())
	a = list(map(int, input().split()))
	dp = [array('h', [10000]) * (n + 1) for _ in range(n + 1)]
	num = [array('h', [-1]) * (n + 1) for _ in range(n + 1)]
	for i in range(n):
		dp[i][i + 1] = 1
		num[i][i + 1] = a[i]
	for sublen in range(2, n + 1):
		for (l, r) in zip(range(n), range(sublen, n + 1)):
			for mid in range(l + 1, r):
				if num[l][mid] == num[mid][r] != -1:
					dp[l][r] = 1
					num[l][r] = num[l][mid] + 1
					break
				dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid][r])
	print(dp[0][-1])
main()


n = int(input())
a = [int(x) for x in input().split()]
dp = [[-1] * (n + 1) for _ in range(n + 1)]
for i in range(n):
	dp[i][i + 1] = a[i]
for leng in range(2, n + 1):
	for l in range(n + 1):
		if l + leng > n:
			continue
		r = l + leng
		for mid in range(l + 1, n + 1):
			if dp[l][mid] != -1 and dp[l][mid] == dp[mid][r]:
				dp[l][r] = dp[l][mid] + 1
dp2 = [float('inf') for _ in range(n + 1)]
for i in range(n + 1):
	dp2[i] = i
	for j in range(i):
		if dp[j][i] != -1:
			dp2[i] = min(dp2[i], dp2[j] + 1)
print(dp2[n])


import sys
input = sys.stdin.readline
n = int(input().strip())
a = [int(x) for x in input().strip().split()]
dp = [[0] * n for i in range(n)]
for i in range(n):
	dp[i][i] = [a[i], 1]
for i in range(1, n):
	for j in range(n - i):
		(v, c) = (-1, i + 1)
		for k in range(i):
			if dp[j][j + k][0] != -1 and dp[j][j + k][0] == dp[j + k + 1][j + i][0]:
				(v, c) = (dp[j][j + k][0] + 1, 1)
				break
			else:
				(v, c) = (-1, min(c, dp[j][j + k][1] + dp[j + k + 1][j + i][1]))
		dp[j][j + i] = [v, c]
print(dp[0][-1][1])


import sys
pl = 1
if pl:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('outpt.txt', 'w')

def li():
	return [int(xxx) for xxx in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())
t = 1
while t > 0:
	t -= 1
	n = fi()
	a = li()
	dp = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		for j in range(i, n):
			if i == j:
				dp[i][j] = a[i]
			elif i == j - 1:
				if a[i] == a[j]:
					dp[i][j] = a[i] + 1
			else:
				for k in range(i, j):
					if dp[i][k] and dp[k + 1][j] and (dp[i][k] == dp[k + 1][j]):
						dp[i][j] = dp[i][k] + 1
						break
	ans = [10 ** 18] * (n + 1)
	ans[-1] = 0
	for i in range(n - 1, -1, -1):
		for j in range(i, n):
			if dp[i][j]:
				ans[i] = min(ans[i], 1 + ans[j + 1])
			else:
				ans[i] = min(ans[i], j - i + 1 + ans[j + 1])
	print(ans[0])


from sys import stdin, stdout
import sys
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().strip().split(' ')))
dp_arr = [[None for i in range(n)] for i in range(n)]
for i in range(n):
	dp_arr[i][i] = (arr[i], 1, arr[i])

def merge_small(c1, c2):
	if c1[1] == 1 and c2[1] == 1:
		if c1[0] == c2[0]:
			return (c1[0] + 1, 1, c1[0] + 1)
		else:
			return (c1[0], 2, c2[0])
	elif c1[1] == 2 and c2[1] == 1:
		if c1[2] == c2[0]:
			if c1[0] == c1[2] + 1:
				return (c1[0] + 1, 1, c1[0] + 1)
			else:
				return (c1[0], 2, c2[2] + 1)
		else:
			return (c1[0], 3, c2[2])
	elif c1[1] == 1 and c2[1] == 2:
		if c1[2] == c2[0]:
			if c2[2] == c2[0] + 1:
				return (c2[2] + 1, 1, c2[2] + 1)
			else:
				return (c2[0] + 1, 2, c2[2])
		else:
			return (c1[0], 3, c2[2])
	elif c1[1] == 2 and c2[1] == 2:
		if c1[2] == c2[0]:
			c1 = (c1[0], 2, c1[2] + 1)
			c2 = (c2[2], 1, c2[2])
			if c1[1] == 2 and c2[1] == 1:
				if c1[2] == c2[0]:
					if c1[0] == c1[2] + 1:
						return (c1[0] + 1, 1, c1[0] + 1)
					else:
						return (c1[0], 2, c2[2] + 1)
				else:
					return (c1[0], 3, c2[2])
		else:
			return (c1[0], 4, c2[2])

def merge_main(c1, c2):
	if c1[1] > 2:
		if c2[1] > 2:
			if c1[2] == c2[0]:
				return (c1[0], c1[1] + c2[1] - 1, c2[2])
			else:
				return (c1[0], c1[1] + c2[1], c2[2])
		else:
			if c2[1] == 1:
				if c1[2] == c2[0]:
					return (c1[0], c1[1], c2[2] + 1)
				else:
					return (c1[0], c1[1] + 1, c2[2])
			if c2[1] == 2:
				if c1[2] == c2[0]:
					if c1[2] + 1 == c2[2]:
						return (c1[0], c1[1], c2[2] + 1)
					else:
						return (c1[0], c1[1] + 1, c2[2])
				else:
					return (c1[0], c1[1] + 2, c2[2])
	elif c2[1] > 2:
		if c1[1] == 1:
			if c1[2] == c2[0]:
				return (c1[2] + 1, c2[1], c2[2])
			else:
				return (c1[2], c2[1] + 1, c2[2])
		if c1[1] == 2:
			if c1[2] == c2[0]:
				if c1[0] == c1[2] + 1:
					return (c1[0] + 1, c2[1], c2[2])
				else:
					return (c1[0], c2[1] + 1, c2[2])
			else:
				return (c1[0], c2[1] + 2, c2[2])
	else:
		return merge_small(c1, c2)
for i1 in range(1, n):
	for j1 in range(n - i1):
		curr_pos = (j1, j1 + i1)
		for k1 in range(j1, j1 + i1):
			res = merge_main(dp_arr[j1][k1], dp_arr[k1 + 1][j1 + i1])
			if dp_arr[j1][j1 + i1] == None or dp_arr[j1][j1 + i1][1] > res[1]:
				dp_arr[j1][j1 + i1] = res
stdout.write(str(dp_arr[0][n - 1][1]) + '\n')


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	inf = 10 ** 9
	n = II()
	aa = LI()
	dp1 = [[-1] * n for _ in range(n)]
	dp2 = [[inf] * n for _ in range(n)]
	for i in range(n):
		dp1[i][i] = aa[i]
		dp2[i][i] = 1
	for w in range(2, n + 1):
		for l in range(n - w + 1):
			r = l + w - 1
			for m in range(l, r):
				if dp1[l][m] != -1 and dp1[l][m] == dp1[m + 1][r]:
					dp1[l][r] = dp1[l][m] + 1
					dp2[l][r] = 1
	for m in range(n):
		for l in range(m + 1):
			for r in range(m + 1, n):
				dp2[l][r] = min(dp2[l][r], dp2[l][m] + dp2[m + 1][r])
	print(dp2[0][n - 1])
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = RLL()
	dp = [[n] * n for i in range(n)]
	rec = [[0] * n for i in range(n)]
	for i in range(n):
		rec[i][i] = arr[i]
		dp[i][i] = 1
	for le in range(2, n + 1):
		for l in range(n):
			r = l + le - 1
			if r > n - 1:
				break
			for m in range(l, r):
				dp[l][r] = min(dp[l][r], dp[l][m] + dp[m + 1][r])
				if rec[l][m] == rec[m + 1][r] and dp[l][m] == dp[m + 1][r] == 1:
					dp[l][r] = 1
					rec[l][r] = rec[l][m] + 1
	print(dp[0][-1])
main()


from sys import stdin, stdout

def dfs(l, r, dp, a_a):
	if l == r:
		return a_a[l]
	if l + 1 == r:
		if a_a[l] == a_a[r]:
			return a_a[l] + 1
		else:
			return -1
	if dp[l][r] != 10 ** 6:
		return dp[l][r]
	dp[l][r] = -1
	for m in range(l, r):
		r1 = dfs(l, m, dp, a_a)
		r2 = dfs(m + 1, r, dp, a_a)
		if r1 > 0 and r1 == r2:
			dp[l][r] = r1 + 1
			return dp[l][r]
	return dp[l][r]

def array_shrinking(n, a_a):
	dp = [[10 ** 6 for _ in range(n)] for _ in range(n)]
	dp2 = [10 ** 6 for _ in range(n)]
	for i in range(n):
		dp2[i] = min(i + 1, dp2[i])
		for j in range(i, n):
			r = dfs(i, j, dp, a_a)
			if r != -1:
				if i > 0:
					dp2[j] = min(dp2[i - 1] + 1, dp2[j])
				else:
					dp2[j] = min(1, dp2[j])
	return dp2[n - 1]
n = int(stdin.readline())
a_a = list(map(int, stdin.readline().split()))
res = array_shrinking(n, a_a)
stdout.write(str(res))


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
INF = 10001
mod = int(1000000000.0) + 7
n = int(data())
a = mdata()
ans = [n]
dp1 = [[0] * n for i in range(n)]
dp2 = [[n] * n for i in range(n)]
for i in range(n - 1, -1, -1):
	dp1[i][i] = a[i]
	dp2[i][i] = 1
	for j in range(i + 1, n):
		for k in range(i, j):
			if dp1[i][k] == dp1[k + 1][j] != 0:
				dp1[i][j] = dp1[i][k] + 1
				dp2[i][j] = 1
			dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k + 1][j])
out(dp2[0][n - 1])


import io
import os
import sys
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(10 ** 5)

def solve(N, A):
	valToLeftRight = defaultdict(lambda : defaultdict(set))
	valToRightLeft = defaultdict(lambda : defaultdict(set))
	for (i, x) in enumerate(A):
		valToLeftRight[x][i].add(i)
		valToRightLeft[x][i].add(i)
	maxVal = 1000 + 10
	for val in range(maxVal):
		for (l, rights) in valToLeftRight[val - 1].items():
			for r in rights:
				l2 = r + 1
				if l2 in valToLeftRight[val - 1]:
					for r2 in valToLeftRight[val - 1][l2]:
						assert l <= r
						assert r + 1 == l2
						assert l2 <= r2
						valToLeftRight[val][l].add(r2)
						valToRightLeft[val][r2].add(l)
				r2 = l - 1
				if r2 in valToRightLeft[val - 1]:
					for l2 in valToRightLeft[val - 1][r2]:
						assert l2 <= r2
						assert r2 == l - 1
						assert l <= r
						valToLeftRight[val][l2].add(r)
						valToRightLeft[val][r].add(l2)
	intervals = defaultdict(list)
	for val in range(maxVal):
		for (l, rights) in valToLeftRight[val].items():
			for r in rights:
				intervals[l].append(r)

	@lru_cache(maxsize=None)
	def getBest(left):
		if left == N:
			return 0
		best = float('inf')
		for right in intervals[left]:
			best = min(best, 1 + getBest(right + 1))
		return best
	return getBest(0)

def tup(l, r):
	return l * 16384 + r

def untup(t):
	return divmod(t, 16384)

def solve(N, A):
	cache = {}

	def f(lr):
		if lr not in cache:
			(l, r) = untup(lr)
			if r - l == 1:
				return tup(1, A[l])
			best = tup(float('inf'), float('inf'))
			for i in range(l + 1, r):
				lSplit = f(tup(l, i))
				rSplit = f(tup(i, r))
				(lLen, lVal) = untup(lSplit)
				(rLen, rVal) = untup(rSplit)
				if lLen != 1 or rLen != 1:
					best = min(best, tup(lLen + rLen, 9999))
				elif lVal == rVal:
					best = min(best, tup(1, lVal + 1))
				else:
					best = min(best, tup(2, 9999))
			cache[lr] = best
		return cache[lr]
	ans = untup(f(tup(0, N)))[0]
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = solve(N, A)
print(ans)


def rr():
	return input().rstrip()

def rri():
	return int(rr())

def rrm():
	return list(map(int, rr().split()))
from collections import defaultdict

def mus(d=0):
	return defaultdict(defaultdict(d))

def ms(x, y, d=0):
	return [[d] * y for i in range(x)]

def ar(x, d=0):
	return [d] * x

def ppm(m, n=0, x=0, y=0):
	print('\n'.join(('\t'.join((str(m[j][i]) for j in range(y or n))) for i in range(x or n))))

def ppa(a, n):
	print('\t'.join(map(str, a[0:n])))

def ppl():
	print('\n+' + '- -' * 20 + '+\n')
INF = float('inf')

def fake_input():
	return ...
dp = ms(501, 501)
dp2 = ar(501, INF)

def read():
	n = rri()
	global arr
	arr = rrm()
	return (arr, n)

def calc_dp(l, r):
	assert l < r
	if l + 1 == r:
		dp[l][r] = arr[l]
		return dp[l][r]
	if dp[l][r] != 0:
		return dp[l][r]
	dp[l][r] = -1
	for i in range(l + 1, r):
		lf = calc_dp(l, i)
		rg = calc_dp(i, r)
		if lf > 0 and lf == rg:
			dp[l][r] = lf + 1
			return dp[l][r]
	return dp[l][r]

def solve(arr, n):
	dp2[0] = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			v = calc_dp(i, j)
			if v > 0:
				dp2[j] = min(dp2[j], dp2[i] + 1)
	ans = dp2[n]
	return ans
input_data = read()
result = solve(*input_data)
print(result)


n = int(input())
li = list(map(int, input().split(' ')))
dp1 = []
for i in range(n):
	lis = [-1] * n
	dp1.append(lis)
dp2 = [0] * n
for i in range(n):
	dp1[i][i] = li[i]
for i in range(n):
	dp2[i] = i + 1
size = 2
while size <= n:
	i = 0
	while i < n - size + 1:
		j = i + size - 1
		k = i
		while k < j:
			if dp1[i][k] != -1:
				if dp1[i][k] == dp1[k + 1][j]:
					dp1[i][j] = dp1[i][k] + 1
			k += 1
		i += 1
	size += 1
i = 0
while i < n:
	k = 0
	while k <= i:
		if dp1[k][i] != -1:
			if k == 0:
				dp2[i] = 1
			else:
				dp2[i] = min(dp2[i], dp2[k - 1] + 1)
		k += 1
	i += 1
print(dp2[n - 1])


import math
input_list = lambda : list(map(int, input().split()))
n = int(input())
a = input_list()
(rows, cols) = (n + 1, n + 1)
dp = [[-1 for i in range(rows)] for j in range(cols)]
for i in range(n):
	dp[i][i] = a[i]
for last in range(1, n):
	for first in range(last - 1, -1, -1):
		for mid in range(last, first, -1):
			if dp[first][mid - 1] != -1 and dp[mid][last] != -1 and (dp[first][mid - 1] == dp[mid][last]):
				dp[first][last] = dp[first][mid - 1] + 1
ans = [0 for i in range(n)]
for i in range(n):
	ans[i] = i + 1
for i in range(n):
	for j in range(i, -1, -1):
		if j - 1 >= 0:
			if dp[j][i] != -1:
				ans[i] = min(ans[i], ans[j - 1] + 1)
		elif dp[0][i] != -1:
			ans[i] = 1
print(ans[n - 1])


n = int(input())
b = [int(_) for _ in input().split()]
d = [[b[i] if i == j else -1 for i in range(n)] for j in range(n)]

def f(i, j):
	if d[i][j] != -1:
		return d[i][j]
	d[i][j] = 0
	for m in range(i, j):
		l = f(i, m)
		if f(m + 1, j) == l and l:
			d[i][j] = l + 1
			break
	return d[i][j]
a = [_ for _ in range(1, n + 1)]
for e in range(1, n):
	for s in range(e + 1):
		if f(s, e):
			a[e] = min(a[e], a[s - 1] + 1 if s > 0 else a[s])
print(a[-1])


def examA():
	T = I()
	ans = []
	for _ in range(T):
		(N, M) = LI()
		if N % M != 0:
			ans.append('NO')
		else:
			ans.append('YES')
	for v in ans:
		print(v)
	return

def examB():
	T = I()
	ans = []
	for _ in range(T):
		N = I()
		A = LI()
		A.sort()
		ans.append(A[::-1])
	for v in ans:
		print(' '.join(map(str, v)))
	return

def examC():
	T = I()
	ans = []
	for _ in range(T):
		(N, K) = LI()
		A = LI()
		sumA = sum(A)
		if sumA == 0:
			ans.append('YES')
			continue
		cur = 0
		L = []
		for i in range(100):
			now = K ** i
			L.append(now)
			cur += now
			if cur >= sumA:
				break
		for i in range(N):
			A[i] *= -1
		heapify(A)
		for l in L[::-1]:
			if not A:
				break
			a = -heappop(A)
			if a < l:
				heappush(A, -a)
			elif a > l:
				heappush(A, -(a - l))
		if not A or heappop(A) == 0:
			ans.append('YES')
		else:
			ans.append('NO')
	for v in ans:
		print(v)
	return

def examD():

	class combination:

		def __init__(self, n, mod):
			self.n = n
			self.fac = [1] * (n + 1)
			self.inv = [1] * (n + 1)
			for j in range(1, n + 1):
				self.fac[j] = self.fac[j - 1] * j % mod
			self.inv[n] = pow(self.fac[n], mod - 2, mod)
			for j in range(n - 1, -1, -1):
				self.inv[j] = self.inv[j + 1] * (j + 1) % mod

		def comb(self, n, r, mod):
			if r > n or n < 0 or r < 0:
				return 0
			return self.fac[n] * self.inv[n - r] * self.inv[r] % mod
	(N, M) = LI()
	ans = 0
	if N == 2:
		print(ans)
		return
	C = combination(M, mod2)
	for i in range(N - 1, M + 1):
		cur = pow(2, N - 3, mod2) * (i - 1) * C.comb(i - 2, N - 3, mod2)
		ans += cur
		ans %= mod2
	print(ans)
	return

def examE():
	N = I()
	A = LI()
	dp = [[-1] * (N + 1) for _ in range(N + 1)]
	for i in range(N):
		dp[i][i + 1] = A[i]
	for l in range(2, N + 1):
		for i in range(N - l + 1):
			for k in range(i + 1, i + l):
				if dp[i][k] >= 1 and dp[i][k] == dp[k][i + l]:
					dp[i][i + l] = dp[i][k] + 1
	L = [inf] * (N + 1)
	for i in range(1, N + 1):
		if dp[0][i] >= 1:
			L[i] = 1
	for i in range(N):
		for k in range(1, N - i + 1):
			if dp[i][i + k] >= 1:
				L[i + k] = min(L[i + k], L[i] + 1)
	ans = L[N]
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math, random
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
examE()


n = int(input())
b = [int(_) for _ in input().split()]
d = [[-1 if i != j else b[i] for i in range(n)] for j in range(n)]
for l in range(1, n):
	for s in range(n - l):
		e = s + l
		for m in range(s, e):
			if d[s][m] == d[m + 1][e] and d[s][m] != -1:
				d[s][e] = d[s][m] + 1
a = [1]
for e in range(1, n):
	t = 4096
	for s in range(e + 1):
		if d[s][e] != -1:
			t = min(t, a[s - 1] + 1 if s > 0 else a[s])
	a.append(t)
print(a[-1])