#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
const int N = 1000005;

int n,ans;
string c;
string pre,suf;
gp_hash_table<string,int> cnt;
void calc(int l,int r){
	if(l==r) return ;
	int mid = (l+r) / 2;
	calc(l,mid);
	calc(mid+1,r);
	
	cnt.clear();
	
	pre = c[mid+1]; suf = c[mid];
	cnt[suf] ++;
	
	for(int i=mid-1;i>=l;i--){
		if(suf.size()&&c[i]==suf[suf.size()-1])
			suf.pop_back();
		else suf += c[i];
		cnt[suf] ++;
	}
	ans += cnt[pre];
	for(int i=mid+2;i<=r;i++){
		if(pre.size()&&c[i]==pre[pre.size()-1])
			pre.pop_back();
		else pre += c[i];
		ans += cnt[pre];
	}
}
signed main(){
	scanf("%lld",&n);
	cin>>c;
	c = " "+c;
	calc(1,n);
	printf("%lld",ans);
	return 0;
}