Genos recently installed the game Zuma on his phone. In Zuma there exists a line of n gemstones, the i-th of which has color ci. The goal of the game is to destroy all the gemstones in the line as quickly as possible.

In one second, Genos is able to choose exactly one continuous substring of colored gemstones that is a palindrome and remove it from the line. After the substring is removed, the remaining gemstones shift to form a solid line again. What is the minimum number of seconds needed to destroy the entire line?

Let us remind, that the string (or substring) is called palindrome, if it reads same backwards or forward. In our case this means the color of the first gemstone is equal to the color of the last one, the color of the second gemstone is equal to the color of the next to last and so on.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 500) — the number of gemstones.

The second line contains n space-separated integers, the i-th of which is ci (1 ≤ ci ≤ n) — the color of the i-th gemstone in a line.

Output

Print a single integer — the minimum number of seconds needed to destroy the entire line.

Examples

Input

3
1 2 1


Output

1


Input

3
1 2 3


Output

3


Input

7
1 4 4 2 3 2 1


Output

2

Note

In the first sample, Genos can destroy the entire line in one second.

In the second sample, Genos can only destroy one gemstone at a time, so destroying three gemstones takes three seconds.

In the third sample, to achieve the optimal time of two seconds, destroy palindrome 4 4 first and then destroy palindrome 1 2 3 2 1.
//package code;
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.awt.Point;
/**
 *
 * @author prabhat // use stringbuilder,TreeSet, priorityQueue, x+y=(x&y + x|y);
 */                                                           //X+y=2*(x&y)+ x^y;
  public class  a
   {
   public static int n,max1=2000005,k,m,q,a[],a1[],mat[][],id,depth[],parent[][],len=22,tin[],tout[],count=0,size[],sum,cnt;
   public static Point[] p1,p2,p;
   public static long mod=(long)1e9+7,nCr[][],suf[][],ans=0,max=Long.MIN_VALUE,dp[],l,r;
   public static boolean isPrime[],visit[][],valid[][];
   public static HashSet<Integer> hash;
   public static PriorityQueue<Integer> pq[];
   public static  ArrayList<Integer> divisor[],prime,adj[],lpf,list[],pri;
   //public static ArrayList<Character> list[];
   public static  TreeMap<Integer,Integer> tmap[];
   public static String s;
   //public static pair[] pa;
   public  static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static PrintWriter pw;
   static int[] x={-1,0,1},y={1,0,-1};

   public static void main(String[] args) throws IOException
   {
	InputReader in = new InputReader(System.in);
	pw=new PrintWriter(System.out);
	n=in.ii();
	a=in.iia(n);
	int[][] dp=new int[n+1][n+1];
	for(int i=0;i<n;i++)dp[i][i]=1;
	for(int l=2;l<=n;l++)
	{
		for(int i=0;i<n-1;i++)
		{
			int j=i+l-1;
			if(j>=n)continue;
			dp[i][j]=1+dp[i+1][j];
			if(l==2)
			{
			  if(a[i]==a[j])dp[i][j]=1;
			}
			else{
				if(a[i]==a[i+1])dp[i][j]=Math.min(dp[i][j],1+dp[i+2][j]);
				for(int k=i+2;k<=j;k++)
				{
					if(a[i]==a[k])
						dp[i][j]=Math.min(dp[i][j],dp[i+1][k-1]+dp[k+1][j]);
				}
			}
		}
	}
   pw.println(dp[0][n-1]);
	pw.close();
   }
  static int gcd1(int x,int y)
  {
    if(x==0)return y;
    else if(y==0)return x;
    else return gcd(y,x%y);	 
  }
 
 static class Edge{
	 String name;
	int  point,goal;
	Edge(String name,int x,int y)
	{
	   this.name=name;
	   point=x;
	   goal=y;
	}
 }  
static int lowerBound(ArrayList<Integer> al,int tar)
{
	   int s=0;
	   int e=al.size()-1;
	   int ans=0;
	   while(s<=e)
	   {
		   int mid=(s+e)/2;
		   if(al.get(mid)<=tar){s=mid+1;ans=mid+1;}
		   else e=mid-1;
	   }
	   return ans;
}

static boolean isVowel(char c)
{
	return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
}

public  static class DSU
{
	int[] parent;
	int[] rank;
	
	int cnt;
	public DSU(int n){
		parent=new int[n];
		rank=new int[n];
		for(int i=0;i<n;i++){
			parent[i]=i;
			rank[i]=1;
		}
		cnt=n;
	}
	int find(int i){
		while(parent[i] !=i){
			parent[i]=parent[parent[i]];
			i=parent[i];
		}
		return i;
	}
	void Union(int x, int y){
		int xset = find(x);
		int yset = find(y);
		if(xset!=yset)
			cnt--;
		
		if(rank[xset]>rank[yset])
		{
			parent[yset] = xset;
		    rank[xset]+=rank[yset];
			rank[yset]=0;
			//return xset;
		}else{
			parent[xset]=yset;
			rank[yset]+=rank[xset];
			rank[xset]=0;
			//return yset;
		}
	
     return;
	}
}


 static int palin(String s)
 {
	String s1=new StringBuilder(s).reverse().toString();
	return s1.equals(s)==true?1:0;
 }
 /*static int dfs(int u, int p) {

	//discover[count1++]=arr[u];  //  it storing color or arr of vertex u
	//discover[count1++]=u;
	//tin[u] = count++;
   int d1=1000000;
   int d2=1000000;
   int cnt=0;
	//parent[u][0] = p==-1?0:p;
	//size[u]++;
	//for (int i = 1; i < len; i++)
	//	parent[u][i] = parent[parent[u][i-1]][i-1];
	for (int v :adj[u])
		if (v != p)
		{
			cnt++;
			depth[v] = depth[u] + 1;
			int y=dfs( v, u);
			if(y<d1)
			{
				d2=d1;
				d1=y;
			}
			else if(y<d2)
			{
				d2=y;
			}
	//		size[u] += size[v];
		}
	if(cnt==0)return 1;
	ans=Math.min(d1+d2,ans);
	return 1+Math.min(d1,d2);
//	if(adj[u].size()==1&&parent[u][0]!=0)last.add(u);
//	tout[u] = count-1;
}
*/

static boolean isParent(int parent, int child) {
	return tin[parent] <= tin[child] && tout[child] <= tout[parent];
}

static int lca(int a, int b) {
	if (isParent(a, b))
		return a;
	if (isParent(b, a))
		return b;
	for (int i = len - 1; i >= 0; i--)
		if (!isParent(parent[a][i], b))
			a = parent[a][i];
	return parent[a][0];
}
static boolean valid(int i,int j)
{
	return i>=0&&i<3&&j>=0&&j<3;
}
 
static int gcd(int a,int b)
{
	while(a!=0)
	{
		int temp=a;
		a=b%a;
		b=temp;
	}
	return b;
}
static void Seive()
{
	a1=new int[max1];
	isPrime=new boolean[max1];
	Arrays.fill(isPrime,true);
	prime=new ArrayList<>();
	divisor=new ArrayList[max1];
	for(int i=1;i<max1;i++)divisor[i]=new ArrayList<Integer>();
    isPrime[0]=isPrime[1]=false;
	for(int i=2;i<(max1);i++)
	{
         if(isPrime[i]){
			 divisor[i].add(i);
			 prime.add(i);
			 a1[i]=1;
			for(int j=2*i;j<max1;j+=i)
			{
				a1[j]++;
				isPrime[j]=false;
				divisor[j].add(i);
			}
		}
	}
}
public static long pow(long n,long p)
{
	 long  result = 1;
	  if(p==0)
	    return 1;

	while(p!=0)
	{
	    if(p%2==1)
	        result *= n;
	    
	    p >>=1;
	    n*=n;
	}
	return result;
}


static  class InputReader
{
   private InputStream stream;
   private byte[] buf = new byte[1024];

   private SpaceCharFilter filter;
    byte inbuffer[] = new byte[1024];
   int lenbuffer = 0, ptrbuffer = 0;
    final int M = (int) 1e9 + 7;
   int md=(int)(1e7+1);
    int[] SMP=new int[md];
   final double eps = 1e-6;
   final double pi = Math.PI;

	PrintWriter out;
   String check = "";
 InputStream   obj = check.isEmpty() ? System.in : new ByteArrayInputStream(check.getBytes());
   public InputReader(InputStream stream)
   {
       this.stream = stream;
   }

    int readByte() {
	        if (lenbuffer == -1) throw new InputMismatchException();
	        if (ptrbuffer >= lenbuffer) {
	            ptrbuffer = 0;
	            try {
	                lenbuffer = obj.read(inbuffer);
	            } catch (IOException e) {
	                throw new InputMismatchException();
	            }
	        }
	        if (lenbuffer <= 0) return -1;
	        return inbuffer[ptrbuffer++];
   }

   public  int read()
   {
       int c = read();
       while (isSpaceChar(c))
           c = read();
       int sgn = 1;
       if (c == '-')
       {
           sgn = -1;
           c = read();
       }
       int res = 0;
       do
       {
           if (c < '0' || c > '9')
               throw new InputMismatchException();
           res *= 10;
           res += c - '0';
           c = read();
       } while (!isSpaceChar(c));
       return res * sgn;
   }

   String is() {
	        int b = skip();
	        StringBuilder sb = new StringBuilder();
	        while (!(isSpaceChar(b))) // when nextLine, (isSpaceChar(b) && b!=' ')
	        {
	            sb.appendCodePoint(b);
	            b = readByte();
	        }
	        return sb.toString();
   }
   public   int ii() {
	        int num = 0, b;
	        boolean minus = false;
	        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
	        if (b == '-') {
	            minus = true;
	            b = readByte();
	        }
	        while (true) {
	            if (b >= '0' && b <= '9') {
	                num = num * 10 + (b - '0');
	            } else {
	                return minus ? -num : num;
	            }
	            b = readByte();
	        }
   }
 public   long il() {
	        long num = 0;
	        int b;
	        boolean minus = false;
	        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
	        if (b == '-') {
	            minus = true;
	            b = readByte();
	        }
	        while (true) {
	            if (b >= '0' && b <= '9') {
	                num = num * 10 + (b - '0');
	            } else {
	                return minus ? -num : num;
	            }
	            b = readByte();
	        }
   }

	    boolean isSpaceChar(int c) {
	        return (!(c >= 33 && c <= 126));
	       }

	      int skip()
	        {
	        int b;
	        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
	        return b;
	        }

	    float nf() {
	        return Float.parseFloat(is());
	    }

	    double id() {
	        return Double.parseDouble(is());
	    }

	    char ic() {
	        return (char) skip();
	    }

	    int[] iia(int n) {
	        int a[] = new int[n];
	        for (int i = 0; i<n; i++) a[i] = ii();
	        return a;
	    }

	    long[] ila(int n) {
	        long a[] = new long[n];
	        for (int i = 0; i <n; i++) a[i] = il();
	        return a;
	    }

	    String[] isa(int n) {
	        String a[] = new String[n];
	        for (int i = 0; i < n; i++) a[i] = is();
	        return a;
	    }


		 long mul(long a, long b) { return a * b % M; }

		/*	long div(long a, long b)
				 {
					return mul(a, pow(b, M - 2,M));

		           }
*/


	    double[][] idm(int n, int m) {
	        double a[][] = new double[n][m];
	        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i][j] = id();
	        return a;
	        }

	    int[][] iim(int n, int m) {
	        int a[][] = new int[n][m];
	        for (int i = 0; i < n; i++) for (int j = 0; j <m; j++) a[i][j] = ii();
	        return a;
          }


   public String readLine() {
       int c = read();
       while (isSpaceChar(c))
           c = read();
       StringBuilder res = new StringBuilder();
       do {
           res.appendCodePoint(c);
           c = read();
       } while (!isEndOfLine(c));
       return res.toString();
   }

   public interface SpaceCharFilter
   {
       public boolean isSpaceChar(int ch);
   }
   public boolean isEndOfLine(int c) {
       return c == '\n' || c == '\r' || c == -1;
   }
}

}
