#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=1e5+10;
int n,a[mxn],lsh[mxn];
int m,p,sa[mxn],rk[mxn],oldrk[mxn],cnt[mxn],id[mxn],st[mxn][25],lg2[mxn],sti[mxn][25];
int get(int l,int r){
	if(l==r)return 114514;
	if(l>r)swap(l,r);
	r--;
	int d=lg2[r-l+1];
	return min(st[l][d],st[r-(1<<d)+1][d]);
}
int geti(int l,int r){
	int d=lg2[r-l+1];
	return max(sti[l][d],sti[r-(1<<d)+1][d]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<=n;i++)cin>>a[i],lsh[i]=a[i];
	reverse(a+1,a+1+n);
	sort(lsh+1,lsh+1+n);
	int ln=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+1+ln,a[i])-lsh;
	m=ln;
	for(int i=1;i<=n;i++)cnt[rk[i]=a[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;p<n;w<<=1,m=p){
		int cur=0;
		for(int i=n-w+1;i<=n;i++)id[++cur]=i;
		for(int i=1;i<=n;i++)if(sa[i]>w)id[++cur]=sa[i]-w;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)cnt[rk[i]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		p=0;
		memcpy(oldrk,rk,sizeof(rk));
		for(int i=1;i<=n;i++){
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i-1]+w]==oldrk[sa[i]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
	} 
	for(int i=1,k=0;i<=n;i++){
		if(rk[i]==n)continue;
		if(k)k--;
		while(a[i+k]==a[sa[rk[i]+1]+k])k++;
		st[rk[i]][0]=k;
	}
	for(int i=1;i<=20;i++){
		for(int x=1;x+(1<<i)-1<n;x++){
			st[x][i]=min(st[x][i-1],st[x+(1<<i-1)][i-1]);
		}
	}
	for(int i=1;i<=n;i++)sti[rk[i]][0]=i;
	for(int i=1;i<=20;i++){
		for(int x=1;x+(1<<i)-1<=n;x++){
			sti[x][i]=max(sti[x][i-1],sti[x+(1<<i-1)][i-1]);
		}
	}
	
	ll ans=1;
	cout<<ans<<'\n';
	for(int i=n-1;i;i--){
		ans+=n-i+1;
		int mx=0;
		if(geti(1,rk[i])>i){
			int l=1,r=rk[i];
			while(l<r){
				int mid=(l+r+1)>>1;
				if(geti(mid,rk[i])>i)l=mid;
				else r=mid-1;
			}
			mx=max(mx,get(l,rk[i]));
		}
		if(geti(rk[i],n)>i){
			int l=rk[i],r=n;
			while(l<r){
				int mid=(l+r)>>1;
				if(geti(rk[i],mid)>i)r=mid;
				else l=mid+1;
			}
			mx=max(mx,get(rk[i],r));
		}
		ans-=mx;
		cout<<ans<<'\n';
	}
	return 0;
}