You are given an array a_1, a_2, ..., 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 ≤ n ≤ 500) — the initial length of the array a.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 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 → 4 3 3 3 → 4 4 3 → 5 3.

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

In the third and fourth tests, you can't perform the operation at all.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class E {

	int[] ints;
	int[][] dp;
	int[][] compress;
	int NO = 1000000;
	
	public static void main(String[] args) throws NumberFormatException, IOException
	{
		new E().run();
	}
	
	public void run() throws NumberFormatException, IOException {
		//how to deal with 3 3 4 4 4
		//bool[][] i,j can you compress i,j to 1
		BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(file.readLine());
		st = new StringTokenizer(file.readLine());
		ints = new int[N];
		dp = new int[N][N];
		compress = new int[N][N];
		for(int[] in:dp)
			Arrays.fill(in, -1);
		for(int[] in: compress)
			Arrays.fill(in, -1);
		for(int i = 0;i<N;i++)
			ints[i] = Integer.parseInt(st.nextToken());
		System.out.println(opt(0,ints.length - 1));
		/*for(int[] in: compress)
		{
			System.out.println(Arrays.toString(in));
		}*/
		//2 cases - either you can make 1 value, or there is a space where you can split 
	}
	
	public int opt(int L, int R)
	{
		if(L == R)
			return dp[L][R] = 1;
		if(dp[L][R] != -1)
			return dp[L][R];
		if(tryCompress(L,R) != NO)
		{
			return dp[L][R] = 1;
		}
		int min = 10000;
		for(int i = L;i<R;i++)
		{
			int left = opt(L, i);
			int right = opt(i+1,R);
			min = Math.min(min, left + right);
		}
		return dp[L][R] = min;
	}
	
	public int tryCompress(int L, int R)//returns what range is compressed to, or NO otherwise
	{
		if(L == R)
			return compress[L][R] = ints[L];
		if(compress[L][R] != -1)
			return compress[L][R];
		for(int i = L;i<R;i++)
		{
			int left = tryCompress(L, i);
			int right = tryCompress(i+1, R);
			if(left != NO && right != NO && left == right)
				return compress[L][R] = left+1;
		}
		return compress[L][R] = NO;
	}
	
	public boolean testSingle(int L, int R)
	{
		int min = 1001;
		int mindex = -1;
		for(int i =L;i<=R;i++)
		{
			if(ints[i] < min)
			{
				min = ints[i];
				mindex = i;
			}
		}
		int rptr = mindex +1;
		int lptr = mindex - 1;
		int lookingFor = min;
		while(true)
		{
			if(rptr != R+1 && ints[rptr] == lookingFor)
			{
				rptr++;
				lookingFor++;
			}else if(lptr != L-1 && ints[lptr] == lookingFor)
			{
				lptr--;
				lookingFor++;
			}else {
				break;
			}
		}
		return lptr == L-1 && rptr == R+1;
	}
	
}
