我的妈呀，首先代码本地能过编译居然不行……然后是一个谜的堆哈希，大样例都过不了，真的美醉了。求调

#include <bits/stdc++.h>
using namespace std;
#define int __int128_t
const int base=131;
const int N=2000005;
const int mod=(long long)1e18+9;
int n,a[N],p[N];
stack<int> s;
unordered_map<int,int> buc;
int qpow(int a,int b){
    int ans=1ll;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
int inv(int x){
    return qpow(x,mod-2)%mod;
}
int read(){
    int x=0; bool f=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            f=1;
            c=getchar();
        }
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return f?-x:x;
}

inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
signed main(){
    //freopen("game4.in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        a[i]=c-'a'+1;
    }
    int h=0,invb=inv(base);
    buc[0]=1;
    for(int i=1;i<=n;i++){
        if(s.empty()){
            s.push(a[i]);
            h=a[i]%mod;
        }
        else if(s.top()==a[i]){
            s.pop();
            h=(h-h%base)*invb%mod;
        }
        else{
            s.push(a[i]);
            h=(h*base+a[i])%mod;
        }
        buc[h]++;
//        write(h);
//        cout<<'\n';
    }
    int ans=0;
    for(auto [num,cnt]:buc){
        ans+=cnt*(cnt-1)/2;
    }
    write(ans);
}