PalSplit

//Soltuie Iacob Tudor
#include<bits/stdc++.h>
using namespace std;
ifstream fin("window.in");
ofstream fout("window.out");
int n,dp[505][505],v[505];
bool dp2[505][505];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>v[i],dp2[i][i]=true,dp[i][i]=1;
    for(int i=1;i<n;i++)dp2[i][i+1]=(v[i]==v[i+1]),dp[i][i+1]=((dp2[i][i+1])?1:2);
    for(int i=3;i<=n;i++){
        for(int j=1;j+i-1<=n;j++){
            dp2[j][j+i-1]=(v[j]==v[j+i-1]&&dp2[j+1][j+i-2]);
        }
    }
    for(int i=3;i<=n;i++){
        for(int j=1;j+i-1<=n;j++){
            dp[j][j+i-1]=1+dp[j+1][j+i-1];
            if(dp2[j][j+i-1])dp[j][j+i-1]=1;
            else{
                for(int k=j;k<j+i-1;k++){
                    dp[j][j+i-1]=min(dp[j][j+i-1],dp[j][k]+dp[k+1][j+i-1]);
                }
                if(v[j]==v[j+i-1]){
                    dp[j][j+i-1]=min(dp[j][j+i-1],dp[j+1][j+i-2]);
                }
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}