#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define fz(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define put(x) putchar(x) #define eoln put('\n') #define space put(' ') #define int long long inline int read(){ int x=0,neg=1; char c=getchar(); while(!isdigit(c)){ if(c=='-')neg=-1; c=getchar(); } while(isdigit(c)) x=x*10+c-'0',c=getchar(); return x*neg; } inline void print(int x){ if(x<0){ putchar('-'); print(abs(x)); return; } if(x<=9)putchar(x+'0'); else{ print(x/10); putchar(x%10+'0'); } } int n,nxt[1000005]; char s[1000005]; inline void getnext(){//求next数组 int j=0; nxt[1]=0; for(int i=2;i<=n;i++){ while(j!=0&&s[j+1]!=s[i]) j=nxt[j]; if(s[j+1]==s[i])j++; nxt[i]=j; } } signed main(){ cin>>n>>s+1; getnext(); int ans=0; fz(i,1,n){ int j=i; while(nxt[j]) j=nxt[j]; if(nxt[i])nxt[i]=j; ans+=i-j; } cout<<ans; return 0; }