#include<iostream>
#include<cstdio>
using namespace std;
char ch[2000005];
int dp[8005][8005];
int main()
{
	int n,s=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>ch[i];
		if (ch[i]==ch[i-1])
		{
			dp[i-1][i]=1;
			s++;
		}
	}
	for(int i=1;i+2<=n;i++)
	{
		if (ch[i]==ch[i+1]&&ch[i+1]==ch[i+2])
		{
			dp[i][i+2]=1;
			s++;
		}
	}
	for(int l=4;l<=n;l++)
	{
		for(int i=1;i+l-1<=n;i++)
		{
			int j=i+l-1;
			for(int k=i+1;k<=j-2;k++)
			{
				if (dp[i][k]==1&&dp[k+1][j]==1)
				{
					dp[i][j]=1;
					s++;
					break;
				}
			}
			if (dp[i][j]==0&&ch[i]==ch[j])
			{
				if (dp[i+1][j]==1||dp[i][j-1]==1||dp[i+1][j-1]==1)
				{
					dp[i][j]=1;
					s++;
				}
			}
		}
	}
//	for(int l=2;l<=n;l++)
//	{
//		for(int i=1;i+l-1<=n;i++)
//		{
//			if (dp[i][i+l-1]==1)
//			{
//				printf("%d %d\n",i,i+l-1);
//			}
//		}
//	}
	printf("%d",s);
	return 0;
}