题意：

思路：

#include <cstdio>
#include <random>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 3e5 + 10;
const int inf = 0x3f3f3f3f;
struct Node{
    int l,r;
    int val,key;
    int size;
}fhq[N];
int cnt,root;
std::mt19937 rnd(233);
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;
}
inline int newnode(int val){
    fhq[++cnt].val = val;
    fhq[cnt].key = rnd();
    fhq[cnt].size = 1;
    return cnt;
}
void update(int now){
    fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1;
}
void split(int now,int val,int &x,int &y){
    if(!now) { x = y = 0;return;}
    if(fhq[now].val<=val){
        x = now;
        split(fhq[now].r,val,fhq[now].r,y);
    }else {
        y = now;
        split(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)       {
        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){
    split(root,val,x,y);
    root = merge(merge(x,newnode(val)),y);
}
void del(int val){
    split(root,val,x,z);
    split(x,val-1,x,y);
    y = merge(fhq[y].l,fhq[y].r);
    root = merge(merge(x,y),z);
}
int getrank(int val){
    split(root,val-1,x,y);
    int res = fhq[x].size+1;
    root = merge(x,y);
    return res;
}
int getnum(int rank){
    int now = root;
    while(now)
    {
        if(fhq[fhq[now].l].size+1==rank)
            break;
        else if(fhq[fhq[now].l].size>=rank)
            now=fhq[now].l;
        else 
        {
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    return fhq[now].val;
}
int pre(int val){
    split(root,val-1,x,y);
    int now = x;
    while(fhq[now].r)
        now = fhq[now].r;
    int res = fhq[now].val;
    root=merge(x,y);
    return res;
}
int nex(int val){
    split(root,val,x,y);
    int now = y;
    while(fhq[now].l)
        now = fhq[now].l;
    int res = fhq[now].val;
    root=merge(x,y);
    return res;
}
int n;
unordered_map<int,int> dep;
int main(){
    insert(-inf),insert(inf);
    dep[-inf] = -1,dep[inf] = -1;
    long long ans = 0;
    scanf("%d",&n);
    for(int i = 1,x;i <= n;i++){
        x = read();
        insert(x);
        dep[x] = max(dep[nex(x)],dep[pre(x)]) + 1;
        ans += dep[x];
        printf("%lld\n",ans);
    }
    return 0;
}