#include <iostream>
using namespace std;
const long long SIZE=2E3+5;
long long dp[SIZE][SIZE]={-1}, a[SIZE];
long long f(long long l, long long r){
    if(l==r){
        dp[l][r]=1;
        return 1;
    }
    if(dp[l][r]!=-1) return dp[l][r];
    dp[l][r]=f(l+1, r)+f(l, r-1)+f(l+1, r-1);
    if(a[l]==a[r]) dp[l][r]+=1+f(l+1, r-1);
    return dp[l][r];
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long n, i, j; cin >> n; for(i=0; i<n; ++i) cin >> a[i];
    for(i=0; i<n; ++i) dp[i][i]=a[i];
    cout << f(0, n-1);
    return 0;
}