用并查集的路径压缩来维护每个位置下一个可用的位置，$find(x)$就是从$x$开始右面第一个可以插入的位置，以此为根据进行查找和更新，插入就把当前并查集指向的位置赋值，然后让并查集指向下一个可用的位置即可。

赛时还有很多其他的AC方式，可以等赛后看看别人的代码。

时间复杂度:接近$O(N+q)$

#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 1 << 20;
vector<int> fa(N + 1);
vector<long long> a(N + 1, -1);

int find(int x){
	if(fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for(int i = 0; i <= N; i++) fa[i] = i;
	int q;
	cin >> q;
	while(q--){
		int op;
		long long x;
		cin >> op >> x;
		int h = x % N;
		if(op == 1){
			int pos = find(h);
			a[pos] = x;
			fa[pos] = find((pos + 1) % N);
		}
		else{
			cout << a[h] << endl;
		}
	}
	return 0;
}