代码很好理解的：

#include<bits/stdc++.h>
#define rank Rank
#define N 100005
using namespace std;
int n,m,x[N],SA[N],rank[N],tp[N],tax[N],Height[N],mins[N][20],lg[N],ans;
vector<int> vec;
void RSort(){
	for(int i=0;i<=m;i++) tax[i]=0;
	for(int i=1;i<=n;i++) tax[rank[tp[i]]]++;
	for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
	for(int i=n;i>=1;i--) SA[tax[rank[tp[i]]]--]=tp[i]; 
}
bool cmp(int *f,int x,int y,int w){return f[x]==f[y]&&f[x+w]==f[y+w];}
void Suffix(){
	for(int i=1;i<=n;i++){rank[i]=x[i];tp[i]=i;}
	m=vec.size();RSort();
	int p=1;
	for(int w=1;p<n;w<<=1,m=p){
		int k=0;
		for(int i=n-w+1;i<=n;i++) tp[++k]=i;
		for(int i=1;i<=n;i++){if(SA[i]>w) tp[++k]=SA[i]-w;}
		RSort();swap(tp,rank);rank[SA[1]]=p=1; 
		for(int i=2;i<=n;i++) rank[SA[i]]=cmp(tp,SA[i],SA[i-1],w)?p:++p;
	} 
	p=0;
	for(int i=1;i<=n;Height[rank[i++]]=p){
		p=p?p-1:p;
		for(int j=SA[rank[i]-1];x[i+p]==x[j+p];p++);
	}
}
void ST(){
	for(int i=1;i<=n;i++) mins[i][0]=Height[i];
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++) mins[i][j]=min(mins[i][j-1],mins[i+(1<<j-1)][j-1]);
	}
}
int lcp(int a,int b){
	a++;
	return min(mins[a][lg[b-a+1]],mins[b-(1<<lg[b-a+1])+1][lg[b-a+1]]);
}
set<int> st;
int main(){
	scanf("%d",&n);
	lg[0]=-1;
	for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++) scanf("%d",&x[i]);
	for(int i=1;i<=n;i++) vec.push_back(x[i]);
	sort(vec.begin(),vec.end());vec.resize(unique(vec.begin(),vec.end())-vec.begin());
	for(int i=1;i<=n;i++) x[i]=lower_bound(vec.begin(),vec.end(),x[i])-vec.begin()+1;
	reverse(x+1,x+n+1);
	Suffix();ST();
	st.insert(0);st.insert(n+1);
	for(int i=n;i>=1;i--){
		st.insert(rank[i]);
		set<int>::iterator it=st.find(rank[i]);
		it--;int a=*it;
		it++;it++;int b=*it;
		ans+=lcp(a,rank[i])+lcp(rank[i],b)-lcp(a,b); 
		printf("%d\n",(n-i+1)*(n-i+2)/2-ans);
	} 
	return 0;
}