这个题用一波FHQ Treap做，不用STL了，正好检验一波手搓的无旋Treap怎么样。

题解：这个题插入操作跟普通的二叉树是相同的，让你找一个数的前序和后继，如果我们用普通的BST，势必会T到天上去，一条链足以卡飞BST，这里用了一波FHQ Treap无旋平衡树来写这个题。
很感谢这个题的输入的数据范围是大于1小于某个数（只知道小于1e6）（参考了zzugzx大佬的想法），所以就可以免去再做一写别的操作了。
我们设置一个最大值一个最小值，目的是为了保证他有前驱和后继，因为你插入一个值，会有4种情况。
1.前驱后继都有
2.有前驱没用后继
3.有后继没有前驱
4.没有后继也没有前驱
所以我们插入一个比较大的值和一个比较小的值，以确保每次插入的值都有前驱和后继，这样的话在我们每次找前驱后继都很方便了。
至于这个FHQ Treap的实现，代码中都写有注释了。

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 11100;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;

int cnt,root;
mt19937 rnd(233);  //随机数
struct Node{
    int l,r,val,key,size;
}fhq[1000010];
int newnode(int val){  //开辟新结点
    fhq[++cnt].val=val;
    fhq[cnt].key=rnd();
    fhq[cnt].size=1;
    return cnt;   //直接返回一个新结点
}

void update(int now){  //push_up更新节点大小（当加入了新结点）
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void spilt(int now,int val,int &x,int &y){ //分裂乘两棵树
    if(!now) x=y=0;  //如果是一颗空树，直接返回x，y是空树即可
    else{
        if(fhq[now].val<=val){  //这里是按值分裂把小于等于val值得分到x树，大于val得分到y树
            x=now; //这个值左孩子上得所有结点都属于x这棵树
            spilt(fhq[now].r,val,fhq[now].r,y);
            //右孩子上大部分都会大于这个值，
            //也有可能会有小于val这个值得，所以我们要继续递归右子树进行查找
        }
        else{
            y=now;   //复读机
            spilt(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}
int merge(int x,int y){   //把两棵树合并起来
    if(!x||!y) return x+y;
    if(fhq[x].key>fhq[y].key){   //既要符合堆得性质，又要符合搜索树得性质
        //我们知道x这棵树上得值全都小于y这颗树上得值，
        // 所以当x得key大于y这个key得时候，y在x得右下方（既要在右边，也要在下面）
        //所以让x得右子树跟y合并
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }
    else{
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}
int x,y,z;
void insert(int val){  //插入某值
    spilt(root,val,x,y);  //先把树按照val值分裂开
    //因为x树都小于等于val，所以我们直接让新结点跟x合并起来
    //再把x树跟y树合并起来
    root=merge(merge(x,newnode(val)),y);
}
int pre(int val){   
    //找前驱，按照val-1分裂此树
    //在他前面的哪个数，一定是在x树上的最右端（最大值）
    spilt(root,val-1,x,y);
    int now=x;
    while (fhq[now].r) now=fhq[now].r;
    int temp=fhq[now].val;
    root=merge(x,y);
    return temp;
}
int nxt(int val){
    //找后继，按照val分裂此树
    //在他后面的树一定是y树上最左边的值（最小值）
    spilt(root,val,x,y);
    int now=y;
    while (fhq[now].l) now=fhq[now].l;
    int temp=fhq[now].val;
    root=merge(x,y);
    return temp;
}
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int deep[1000010];
int main() {
    int n;
    cin>>n;
    insert(1000000),insert(0);
    deep[1000000]=deep[0]=-1;
    long long ans=0;
    while(n--){
        int v;
        v=read();
        deep[v]=max(deep[pre(v)],deep[nxt(v)])+1;
        insert(v);
        ans+=deep[v];
        printf("%lld\n",ans);
    }

    return 0;
}