description：

对于一颗二叉树每次进行insert操作 ，输出当前节点的深度和

solution：

如果维护普通的BST的话有可能因为树退化成链导致TLE，防止树退化成链可以大力套平衡树上去是可以ac的.但这题可以不用这么麻烦，通过观察，我们可以知道插入结点时会有四种情况
1.有pre和suc
2.有pre无suc
3.无pre有suc
4.两个都没
维护一个dep数组 来代表结点深度
维护set代表树的情况 通过二分来找当前点为以上四种情况哪一种 对应分别处理。

code：

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x, a) memset(x, a, sizeof(x));
#define sca(a) scanf("%d", &a)
#define lowbit(x) x&(-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lson v << 1
#define rson v << 1 | 1
#define pii pair<int, int>

inline void read(int &x)
{
    x=0;
    int flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    x *= flag_read;
}

void out(int x){
    if(x > 9){
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

const int N = 3e5 + 50;
set <int> s;
int dep[N],n;

int main(){
    ios::sync_with_stdio(0);
    int n;cin >> n;

    LL res = 0;

    while(n --){
        int x;cin >> x;

        if(s.size() == 0){// 没有结点
            cout << 0 << '\n';
            s.insert(x);
            continue;
        }

        auto it = s.lower_bound(x);

        if(*it == x){
            cout << res << '\n';
            continue;
        }

        if(it == s.begin()){// pre
            dep[x] = dep[*it] + 1;
            res += dep[x];
        }

        else if(it == s.end()){// suc
            -- it;
            dep[x] = dep[*it] + 1;
            res += dep[x];
        }

        else{// pre & suc
            dep[x] = dep[*it] + 1;
            -- it;
            dep[x] = max(dep[x],dep[*it] + 1);
            res += dep[x];
        }
        s.insert(x);

        cout << res << '\n';
    }
    return 0;
}