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

const int N = 2e5 + 10, inf = 2e9;

struct node {
	int l, r, v;
}tree[N * 8];

int n;
int a[N], c[N];
int f[N], m[N];

void push_up(int u) {
	tree[u].v = tree[u << 1].v + tree[u << 1 | 1].v;
}

void build(int u,int l,int r) {
	tree[u].l = l, tree[u].r = r;
	if(l == r) {
		tree[u].v = 1;
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	push_up(u);
}

void modify(int u,int x,int d) {
	if(tree[u].l == tree[u].r) {
		tree[u].v = d;
		return;
	}
	int mid = tree[u].l + tree[u].r >> 1;
	if(x <= mid) modify(u << 1, x, d);
	else modify(u << 1 | 1, x, d);
	push_up(u);
}

int query(int u,int x) {
//	cout << tree[u].l << " " << tree[u].r << endl;
	if(tree[u].l == tree[u].r) {
//		cout << "dsd:" << tree[u].l << endl;
		return tree[u].l;
	}
	int mid = tree[u].l + tree[u].r >> 1;
	if(x <= tree[u << 1].v) return query(u << 1, x);
	else query(u << 1 | 1, x - tree[u << 1].v);
}

signed main() {
	scanf("%lld", &n);
	for(int i = 1;i <= n;i++) {
		scanf("%lld", &a[i]);
	}
	
	build(1, 1, n);
	
	for(int i = n;i >= 1;i--) {
		int tot = query(1, a[i] + 1);
//		cout << tot << " " << a[i] + 1 << endl;
		c[tot] = i;
		modify(1, tot, 0);
	}
	
//	for(int i = 1;i <= n;i++) {
//		cout << c[i] << " ";
//	}
//	cout << endl;
	
	for(int i = 1;i <= n;i++) {
		m[c[i]] = i;
		f[i] = inf;
	} 
	
	int len = 0;
	f[0] = 0;
	for(int i = 1;i <= n;i++) {
		int l = 0, r = len;
		while(l < r) {
			int mid = l + r + 1 >> 1;
			if(f[mid] <= m[i]) l = mid;
			else r = mid - 1;
		}
		if(l == len) f[++len] = m[i];
		else f[l + 1] = min(f[l + 1], m[i]);
		printf("%lld\n", len);
	}
	
	return 0;
}

主要思路是用线段树倒序处理插入操作，然后正常二分 LIS 求答案。