又是一道后缀数组题啊。。。

先理清后缀数组如何实现吧，

通过第一关键字，也就是当前$i$的排名$x_i$，来计算出第二关键字$y$，其中$y_i$表示在第二关键字中排名为$i$的编号为$y_i$。

处理的时候倒叙处理其实就是让第一关键字相同的，第二关键字大的先弹出，这里要注意！

还记得$height$数组吗？也就是用来记录排名相近的两个后缀的最长公共长度，有定理:$height[rk[i]]\ge height[rk[i-1]]-1$，具体证明可以参照这里。

如果一次性全部插入，其实答案就是$\frac{n*(n+1)}{2}-\sum\max\{height[rk[i]],height[rk[i]+1]\}$

因此只要统计重复的串的数量减去就好了。

现在是分步插入的话，把串反转之后其实就是多一个后缀$s$。

考虑它的$prv,nxt$，重复贡献变成了$lcp(s,prv)+lcp(s,nxt)-lcp(prv,nxt)$。

只要考虑如何考虑快速计算$lcp$就好了，因为$lcp$具有传递性，用$ST$表搞一下就好了.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5,Max=1e9,M=1010;
const ll inf=123456789123456789ll;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct Splay
{
    struct node{int f,son[2],d;}t[N];int len,root;
    void add(int d,int f){t[++len]=(node){f,{0,0},d};t[f].son[d>t[f].d]=len;}
    void rotate(int p,int w)
    {
        int f=t[p].f,gf=t[f].f;
        int r=t[p].son[w],R=f;t[R].son[w^1]=r;if(r)t[r].f=R;
        r=p;R=gf;t[R].son[t[R].son[1]==f]=r;t[r].f=R;
        r=f;R=p;t[R].son[w]=r;t[r].f=R;
    }
    void splay(int p,int rt)
    {
        while(t[p].f!=rt)
        {
            int f=t[p].f,gf=t[f].f;
            if(gf==rt)rotate(p,t[f].son[0]==p);
            else
            {
                if(t[f].son[0]==p&&t[gf].son[0]==f)rotate(f,1),rotate(p,1);
                else if(t[f].son[1]==p&&t[gf].son[0]==f)rotate(p,0),rotate(p,1);
                else if(t[f].son[0]==p&&t[gf].son[1]==f)rotate(p,1),rotate(p,0);
                else rotate(f,0),rotate(p,0);
            }
        }
        if(!rt)root=p;
    }
    int get_id(int d)
    {
        int p=root;
        while(t[p].d!=d)
        {
            if(d<t[p].d)
            {
                if(!t[p].son[0])break;
                p=t[p].son[0];
            }
            if(d>t[p].d)
            {
                if(!t[p].son[1])break;
                p=t[p].son[1];
            }
        }
        return p;
    }
    void ins(int d)
    {
        if(!root){add(d,0);root=len;return ;}
        int p=get_id(d);add(d,p);splay(len,0);
    }
    void del(int d)
    {
        int p=get_id(d);splay(p,0);
        if(!t[p].son[0]&&!t[p].son[1])root=0,len=0;
        else if(t[p].son[1]&&!t[p].son[0])t[root=t[p].son[1]].f=0;
        else if(t[p].son[0]&&!t[p].son[1])t[root=t[p].son[0]].f=0;
        else
        {
            int R=t[p].son[0];while(t[R].son[1])R=t[R].son[1];splay(R,p);
            int r=t[p].son[1];t[R].son[1]=r;t[r].f=R;t[root=R].f=0;splay(R,0);
        }
    }
    int nxt(int d)
    {
        int p=get_id(d);splay(p,0);
        if(t[p].d<=d&&t[p].son[1])
            for(p=t[p].son[1];t[p].son[0];p=t[p].son[0]);
        if(t[p].d<=d)return -1;
        return t[p].d;
    }
    int prv(int d)
    {
        int p=get_id(d);splay(p,0);
        if(t[p].d>=d&&t[p].son[0])
            for(p=t[p].son[0];t[p].son[1];p=t[p].son[1]);
        if(t[p].d>=d)return -1;
        return t[p].d;
    }
}spl;
int a[N],n,m,sa[N],wa[N],wb[N],wv[N],height[N],c[N],rk[N];
bool same(int *x,int a,int b,int l){return x[a]==x[b]&&x[a+l]==x[b+l];}
void SA()
{
    int *x=wa,*y=wb,*t;
    for(int i=1;i<=n;i++)++c[x[i]=a[i]];
    for(int i=2;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i;i--)sa[c[x[i]]--]=i;
    for(int j=1,p=0;p<n;j<<=1,m=p)
    {
        p=0;for(int i=n-j+1;i<=n;i++)y[++p]=i;
        for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)++c[wv[i]=x[y[i]]];
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i;i--)sa[c[wv[i]]--]=y[i];
        p=1;t=x;x=y;y=t;x[sa[1]]=1;
        for(int i=2;i<=n;i++)
            x[sa[i]]=same(y,sa[i],sa[i-1],j)?p:++p;
    }
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1,j,k=0;i<=n;height[rk[i++]]=k)
        for(k?--k:0,j=sa[rk[i]-1];a[j+k]==a[i+k];++k);
}
int f[N][18],Log[N];
void ST()
{
    for(int i=1;i<n;i++)f[i][0]=height[i+1];
    for(int i=2;i<n;i++)Log[i]=Log[i>>1]+1;
    for(int t=1;t<=17;t++)
        for(int i=1;i+(1<<t)<=n;i++)
            f[i][t]=min(f[i][t-1],f[i+(1<<(t-1))][t-1]);
}
int arr[N],len;
inline int lcp(int x,int y)
{
    if(x>y)swap(x,y);
    int t=Log[y-x];return min(f[x][t],f[y-(1<<t)][t]);
}
inline int get(int d)
{
    int l=1,r=len;
    while(l<r)
    {
        int mid=l+r>>1;
        if(arr[mid]<d)l=mid+1;
        else r=mid;
    }
    return l;
}
int main()
{
    //freopen("incantation3.in","r",stdin);
    //freopen("incantation3.ans","w",stdout);
    qr(n);
    for(int i=n;i;i--)qr(a[i]),arr[i]=a[i];
    sort(arr+1,arr+n+1);
    for(int i=1;i<=n;i++)if(i==1||arr[i]!=arr[i-1])arr[++len]=arr[i];
    for(int i=1;i<=n;i++)a[i]=get(a[i]);ll cnt=0;
    m=1e5;SA();ST();
    for(int i=n;i;i--)
    {
        int prv=spl.prv(rk[i]),nxt=spl.nxt(rk[i]);
        if(prv!=-1&&nxt!=-1)cnt+=lcp(prv,nxt);
        if(prv!=-1)cnt-=lcp(prv,rk[i]);
        if(nxt!=-1)cnt-=lcp(rk[i],nxt);
        spl.ins(rk[i]);cnt+=n-i+1;qw(cnt);puts("");
    }
    return 0;
}