1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

// Code By Chen Qiqian on 2018.08.10
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

inline int min(int a,int b){return a>b?b:a;}

int n,m;
const int MAXN = 1000100,logn = 20;

namespace SA{
int s[MAXN],sa[MAXN],rk[MAXN],x[MAXN],y[MAXN],ht[MAXN];
int cnt[MAXN];
void get_SA(int n,int m){
    for(int i = 0;i<m;i++) cnt[i] = 0;
    for(int i = 0;i<n;i++) cnt[s[i]]++;
    for(int i = 1;i<m;i++) cnt[i] += cnt[i-1];
    for(int i = n-1;~i;--i) sa[--cnt[s[i]]] = i;
    m = rk[sa[0]] = 0;
    for(int i = 1;i<n;i++) rk[sa[i]] = (s[sa[i]]!=s[sa[i-1]])?++m:m; 
    for(int j = 1;;j<<=1){
        if(++m == n) break;
        for(int i = 0;i<j;i++) y[i] = n-j+i;
        for(int i = 0,k = j;i<n;i++) if(sa[i]>=j) y[k++] = sa[i]-j;
        for(int i = 0;i<n;i++) x[i] = rk[y[i]];
        for(int i = 0;i<m;i++) cnt[i] = 0;
        for(int i = 0;i<n;i++) cnt[x[i]]++;
        for(int i = 1;i<m;i++) cnt[i] += cnt[i-1];
        for(int i = n-1;~i;--i) sa[--cnt[x[i]]] = y[i],y[i] = rk[i];
        m = rk[sa[0]] = 0;
        for(int i = 1;i<n;i++) rk[sa[i]] = (y[sa[i]]!=y[sa[i-1]] || y[sa[i]+j]!=y[sa[i-1]+j])?++m:m;
    }
}
void getheight(int n){
    for(int i = 0, h = ht[0] = 0;i<n;i++){
        int j = sa[rk[i]-1];
        while(i+h<n&&j+h<n&&s[i+h]==s[j+h]) h++;
        if(ht[rk[i]] = h) --h;
    }
}
void build(int n){
    ++n;
    get_SA(n,4);
    getheight(n);
}
}
int _log[MAXN];

namespace ST{
int minn[MAXN][logn];
void build(int n,int *num){
    for(int i = 1;i<=n;i++)
        _log[i] = _log[i-1] + ((i==(1<<(_log[i-1]+1)))?1:0);
    int l = _log[n];
    for(int i = 0;i<=n;i++) minn[i][0] = num[i];
    for(int j = 1;j<=l;j++){
        for(int i = 0;i+(1<<(j-1))<=n;i++){
            minn[i][j] = min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
        }
    }
}    
int query(int l,int r){
    int t = _log[r-l+1];
    return min(minn[l][t],minn[r-(1<<t)+1][t]);
}
}

int lcp(int x,int y){
    if(x == y) return n-x+1;
    x = SA::rk[x],y = SA::rk[y];
    if(x > y) swap(x,y);
    return ST::query(x+1,y);
}

char s[MAXN];

void init(){
    scanf("%d\n",&m);
    fread(s,MAXN,1,stdin);
    for(int i = 0;i<m;i++) SA::s[n++] = s[i] - ('0'-1);
    reverse(s,s+n);
    SA::s[n++] = 3;
    for(int i = 0;i<m;i++) SA::s[n++] = (s[i]^1) - ('0'-1);
    SA::s[n] = 0;
    SA::build(n);
    ST::build(n+1,SA::ht);
}

void solve(){
    long long ans = 0;
    for(int i = 0;i<m;i++){
        ans += lcp(i+1,n-i-1);
    }
    printf("%lld\n",ans);
}

int main(){
    init();
    solve();
    return 0;
}