#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=5e5+10;
int n,P=2333;
long long ans;
string s,rs;
ull p[N],h[N],rh[N];
void hw(int x){
	int l=0,r=min(x,n-x);
	while(l<r){
		int mid=(l+r+1)/2;
		if((h[x+mid]-h[x-mid]*p[2*mid])==(rh[x-mid+1]-rh[x+mid+1]*p[2*mid]))l=mid;
		else r=mid-1;
	}
	ans+=l;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>s[i];
	for(int i=1;i<=n;i++){
		if(s[i]=='1')rs[i]='0';
		else rs[i]='1';
	}
	p[0]=1;
	for(int i=1;i<=n;i++)p[i]=p[i-1]*P;
	for(int i=1;i<=n;i++)h[i]=h[i-1]*P+(s[i]-'0');
	for(int i=n;i>=1;i--)rh[i]=rh[i+1]*P+rs[i]-'0';
	for(int i=1;i<=n-1;i++)hw(i);
	cout<<ans;
	return 0;
} 

题目--