果然SA比SAM+map快。
首先这是SAM裸题，然而SA求本质不同子串个数也很容易。考虑倒着建SA，这样没错加一个字符就变成加一个后缀，其他后缀都不变，那么i的答案就是只考虑前i个后缀的答案。搞个双向链表，每次删一个后缀并RMQ更新答案。
（SAM+map复杂度可能是错的，但是我不清楚）
#include<algorithm>
#include<cstdio>
#define lb lower_bound
using namespace std;
const int N=1e5+5;
typedef int arr[N];
arr sa,r,f[17],c,v,s,t,p,q;
typedef long long ll;
ll b,z[N];
void pre(int*s,int n){
for(int i=0;i<n;++i)
++c[s[i]];
for(int i=1;i<n;++i)
c[i]+=c[i-1];
for(int i=n-1;~i;--i)
sa[--c[s[i]]]=i;
int m=0;
for(int i=1;i<n;++i)
r[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)
v[i]=n-j+i;
for(int i=0;i<m;++i)
c[i]=0;
for(int i=0,k=j;i<n;++i){
if(sa[i]>=j)
v[k++]=sa[i]-j;
++c[r[i]];
}
for(int i=1;i<m;++i)
c[i]+=c[i-1];
for(int i=n-1;~i;--i)
sa[--c[r[v[i]]]]=v[i],v[i]=r[i];
m=r[sa[0]]=0;
for(int i=1;i<n;++i)
r[sa[i]]=v[sa[i]]!=v[sa[i-1]]||v[sa[i]+j]!=v[sa[i-1]+j]?++m:m;
}
}
int ask(int i,int j){
int k=__lg(j-i+1);
return min(f[k][i],f[k][j-(1<<k)+1]);
}
struct buf{
char z[9<<17],*s;
buf():s(z){
z[fread(z,1,sizeof z,stdin)]=0;
}
operator int(){
int x=0;
while(*s<48)++s;
while(*s>32)
x=x*10+*s++-48;
return x;
}
}it;
int main(){
int n=it;
for(int i=n-1;~i;--i)
s[i]=t[i]=it;
sort(t,t+n);
for(int i=0;i<n;++i)
s[i]=lb(t,t+n,s[i])-t+1;
pre(s,n+1);
for(int i=0,j=0;i<n;++i){
if(j)--j;
while(s[i+j]==s[sa[r[i]-1]+j])++j;
f[0][r[i]]=j;
}
for(int j=1;n>>j;++j)
for(int i=0;i+(1<<j)-1<=n;++i)
f[j][i]=min(f[j-1][i],f[j-1][i+(1<<j-1)]);
for(int i=1;i<=n;++i)
b+=n-sa[i]-f[0][i];
for(int i=n;i>1;--i)
p[i]=i-1;
for(int i=1;i<n;++i)
q[i]=i+1;
for(int i=0;i<n;++i){
int j=r[i],k=0;
if(p[j])k=max(k,ask(p[j]+1,j));
if(q[j])k=max(k,ask(j+1,q[j]));
z[i]=b,b-=n-i-k;
p[q[j]]=p[j];
q[p[j]]=q[j];
}
for(int i=n-1;~i;--i)
printf("%lld\n",z[i]);
}