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.

/*
 * Code Author: Mihir Shah
 * DA-IICT
 */
import java.io.*;
import java.math.*;
import java.util.*;

public class TestClass {

	InputReader in;
	PrintWriter out;

	TestClass() throws IOException {
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		// in = new InputReader(new FileInputStream("output_.txt"));
		// out = new PrintWriter(new File("output_.txt"));
		solve();
		out.close();
	}

	public static void main(String args[]) {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new TestClass();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	// --------------------My Code Starts Here----------------------
	int mod = (int) 1e9 + 7;

	public void solve() throws IOException {
		int n = in.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++)
			arr[i] = in.nextInt();
		int[][] dp = new int[n][n];
		/*
		for(int i = n; i > 0; i--) {
			for(int j = n; j >= i; j--) {
				if(i == j)
					dp[i][j] = 1;
				else {
					int secondArg = (int) 1e9;
					for(int k = (i + 1); k <= n; k++) {
						if(arr[k] == arr[i]) {
							if(k != n)
								secondArg = Math.min(secondArg, dp[i + 1][k -1] +
										dp[k + 1][j]);
							else
								secondArg = Math.min(secondArg, dp[i + 1][k - 1]);
						}
					}
					if(i != n && arr[i + 1] == arr[i])
						secondArg = Math.min(secondArg, dp[i + 2][j] + 1);
					// out.println(" second " + secondArg + " i j " + i +" "+ j);
					dp[i][j] = Math.min(1 + dp[i + 1][j], secondArg);
				}
			}
		}
		*/
		
		for(int i = n - 1; i >= 0; i--) {
			for(int j = i; j < n; j++) {
				if(i == j) {
					dp[i][j] = 1;
					continue;
				}
				if(j == (i + 1)) {
					dp[i][j] = (arr[i] == arr[j] ? 1 : 2);
					continue;
				}
				dp[i][j] = (int) 1e9;
				for(int k = (i); k < j; k++) {
					dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
				}
				if(arr[i] == arr[j]) {
					dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
				}
			}
		}
		/*
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				out.print(dp[i][j] + " ");
			}
			out.println();
		}
		*/
		out.println(dp[0][n - 1]);
	}

	// ---------------------My Code Ends Here-----------------------
	static class Pair implements Comparable<Pair> {
		int x;
		int y;
		int i;
		long size;
		int pos;

		Pair(int xx, int yy) {
			x = xx;
			y = yy;
		}

		@Override
		public int compareTo(Pair o) {
			if (Long.compare(this.x, o.x) != 0)
				return -Long.compare(this.x, o.x);
			else
				return Long.compare(this.y, o.y);
		}
	}

	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public final int nextInt() throws IOException {
			return (int) nextLong();
		}

		public final long nextLong() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
				if (c == -1)
					throw new IOException();
			}
			boolean negative = false;
			if (c == '-') {
				negative = true;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return negative ? (-res) : (res);
		}

		public final int[] readIntBrray(int size) throws IOException {
			int[] arr = new int[size];
			for (int i = 0; i < size; i++)
				arr[i] = nextInt();
			return arr;
		}

		public final String next() throws IOException {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final String nextLine() throws IOException {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (c != '\n' && c != -1);
			return res.toString();
		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}
}