rt. 洛谷 IDE 跑样例出来是 0 2 3

#include<bits/stdc++.h>
using namespace std;

long long read()
{
    long long 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 << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s * w;
}

void write(long long a)
{
    if(a < 0) putchar('-'),a = -a;
    if(a > 9) write(a / 10);
    putchar(a % 10 + '0');
}

const int N = 1e6 + 10,inf = 2147483647;

long long n,a,x,y,z,opt;

struct FHQ
{

long long tot,root;
long long maxa[N],fa[N],val[N],dat[N],size[N],son[N][2];

void pushup(long long p)
{
    size[p] = size[son[p][0]] + size[son[p][1]] + 1;
    if(son[p][0]) fa[son[p][0]] = p;
    if(son[p][1]) fa[son[p][1]] = p;
    maxa[p] = max(maxa[son[p][0]],max(maxa[son[p][1]],val[p]));
}

void split_val(long long p,long long k,long long &x,long long &y)
{
    if(p == 0) {x = y = 0;return;}
    if(val[p] <= k) x = p,split_val(son[p][1],k,son[p][1],y);
    else y = p,split_val(son[p][0],k,x,son[p][0]);
    pushup(p);
}

void split_rank(long long p,long long k,long long &x,long long &y)
{
    if(p == 0) {x = y = 0;return;}
    if(size[son[p][0]] < k) x = p,split_rank(son[p][1],k - size[son[p][0]] - 1,son[p][1],y);
    else y = p,split_rank(son[p][0],k,x,son[p][0]);
    pushup(p);
}

long long merge(long long u,long long v)
{
    if(u == 0 || v == 0) return u + v;
    if(dat[u] < dat[v])
    {
        son[u][1] = merge(son[u][1],v);
        pushup(u);
        return u;
    }
    else
    {
        son[v][0] = merge(u,son[v][0]);
        pushup(v);
        return v;
    }
}

long long New(long long x)
{
    val[++tot] = maxa[tot] = maxa[x] + 1,size[tot] = 1,dat[tot] = rand();
    return tot;
}

void insert(long long a)
{
    split_val(root,a,x,y);
    root = merge(merge(x,New(x)),y);
}

void remove1(long long a) // 删除所有点
{
    split_val(root,a,x,z);
    split_val(x,a - 1,x,y);
    root = merge(x,z);
}

void remove2(long long a) // 删除某一点
{
    split_val(root,a,x,z);
    split_val(x,a - 1,x,y);
    y = merge(son[y][0],son[y][1]);
    root = merge(merge(x,y),z);
}

long long get_node(long long p,long long k)
{
    while(1)
    {
        if(k <= size[son[p][0]]) p = son[p][0];
        else if(k == size[son[p][0]] + 1) return p;
        else k -= size[son[p][0]] + 1,p = son[p][1];
    }
}

long long get_val(long long p,long long k){return val[get_node(p,k)];}

long long get_rank(long long a)
{
    split_val(root,a - 1,x,y);
    long long k = size[x] + 1;
    root = merge(x,y);
    return k;
}

long long get_pos(long long p)
{
    long long res = size[son[p][0]] + 1;
    while(fa[p])
    {
        if(p == son[fa[p]][1]) res += size[son[fa[p]][0]] + 1;
        p = fa[p];
    }
    return res;
}

long long get_pre(long long a)
{
    split_val(root,a - 1,x,y);
    long long tmp = get_val(x,size[x]);
    root = merge(x,y);
    return tmp;
}

long long get_next(long long a)
{
    split_val(root,a,x,y);
    long long tmp = get_val(y,1);
    root = merge(x,y);
    return tmp;
}

}tree;

int main()
{
    // freopen("input.in","r",stdin);
    n = read();
    while(n--)
    {
        a = read();
        tree.insert(a);
        write(tree.maxa[tree.root]),putchar('\n');
    }
    return 0;
}