We call a $$$\texttt{01}$$$ string $$$s$$$ of length $$$n$$$ good, if and only if:

• $$$\forall i \in [1,n],s_i \ne s_{n-i+1}$$$.

Given a $$$\texttt{01}$$$ string $$$s$$$, calculate how many substrings in $$$s$$$ are good.

$$$n \le 5 \times 10^5$$$.

/**
 *    author: sunkuangzheng
 *    created: 24.01.2024 15:12:52
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 2e6+5;
using namespace std;
int T,n,m,sa[N],rk[N],ok[N],h[N],st[22][N];string s;
void los(){
    cin >> n >> s,s = s + '#' + string(s.rbegin(),s.rend());
    for(int i = n + 1;i < s.size();i ++) s[i] ^= 1;
    auto SA = [&](string &s,int &n){
        s = " " + s,n = s.size() - 1;
        for(int i = 1;i <= n;i ++) sa[i] = i,rk[i] = s[i];
        for(int j = 1;j < n;j *= 2){
            for(int i = 1;i <= n;i ++) ok[i] = rk[i]; int p = 0;
            sort(sa+1,sa+n+1,[&](int x,int y){return rk[x] < rk[y] || rk[x] == rk[y] && rk[x + j] < rk[y + j];});
            auto cmp = [&](int x,int y){return ok[x] == ok[y] && ok[x + j] == ok[y + j];};
            for(int i = 1;i <= n;i ++) if(cmp(sa[i],sa[i-1])) rk[sa[i]] = p; else rk[sa[i]] = ++p;
        }for(int i = 1,k = 0;i <= n;h[rk[i ++]] = k) for(k --,k = max(k,0);s[i + k] == s[sa[rk[i] - 1] + k];k ++);
        for(int i = 1;i <= n;i ++) st[0][i] = h[i];
        for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
            st[j][i] = min(st[j-1][i],st[j-1][i + (1 << j - 1)]);
    };SA(s,m);
    auto lcp = [&](int i,int j){
        if(i = rk[i],j = rk[j],i > j) swap(i,j); assert(i != j);
        int k = __lg(j - i);
        return min(st[k][i+1],st[k][j-(1<<k)+1]);
    };auto get = [&](int i){return n + 2 + n - i;};
    ll ans = 0;
    for(int i = 1;i < n;i ++) ans += lcp(get(i),i + 1);
    cout << ans;
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=5e5,base=1e9+7;
char s[N+10];
ull h1[N+10],h2[N+10],p[N+10];
bool t1[N+10],t2[N+10];
int n; 
void init()
{
	p[0]=1ull;
	for(int i=1;i<=n;i++) p[i]=p[i-1]*base;
	for(int i=1;i<=n;i++) h1[i]=h1[i-1]*base+(s[i]=='1');
	for(int i=1;i<=n;i++) h2[i]=h2[i-1]*base+(s[n-i+1]=='0');
}
ull hs(ull *h,int l,int r) {return h[r]-h[l-1]*p[r-l+1];}
bool check(int l,int r) {return hs(h1,l,r)==hs(h2,n-r+1,n-l+1);}
int erfen(int i)
{
	int l=0,r=min(i,n-i),ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(i-mid+1,i+mid)) 
		{
			l=mid+1;
			ans=mid;
		} 
		else r=mid-1;
	}
	return ans;
}
int main()
{
	ll ans=0;
	scanf("%d%s",&n,s+1); 
	init();
	for(int i=1;i<n;i++) ans+=erfen(i);
	printf("%lld",ans);
	return 0;
}