rt，样例能过

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=10000000000000061;
ll n,a[2000006];
ll hs[2000006],ans=0,k=33;
map<ll,ll>mp;
string ss;
stack<ll>s,c;
set<ll>S;
int main(){
	cin>>n>>ss;
	ss="*"+ss;
	S.insert(0),mp[0]++;
	for(ll i=1;i<=n;i++){
		a[i]=ss[i]-'a';
		if(s.empty()){
			s.push(a[i]),c.push(i);
			hs[i]=(hs[i-1]*k-a[i]+2)%mod;
			S.insert(hs[i]);
			mp[hs[i]]++;
		}else{
			if(s.top()==a[i]){
				hs[i]=hs[c.top()-1];
				mp[hs[i]]++;
				s.pop(),c.pop();
			}else{
				s.push(a[i]),c.push(i);
				hs[i]=(hs[i-1]*k-a[i]+2)%mod;
				S.insert(hs[i]);
				mp[hs[i]]++;
			}
		}
//		cout<<hs[i]<<" ";
	}
//	cout<<endl;
	for(auto i:S){
		ans+=(mp[i]*(mp[i]-1)/2);
	}
	cout<<ans;
}