大家帮帮我这个蒟蒻吧，

这个问题很逆天，本蒟蒻检查不出来。

题目

我小数据没过大数据过了，这很逆天。

记录

code:

#include<bits/stdc++.h>
using namespace std;
long long n;
struct node{
	long long val,sum,ls,rs,cnt,fa;
}tr[200001];
long long cnt=1;
void push(long long i) {
	tr[i].cnt=tr[tr[i].ls].cnt+tr[tr[i].rs].cnt+1;
}
void rotate(long long i) {
	if(tr[i].ls||tr[i].rs) {
		if(tr[tr[i].ls].cnt>tr[tr[i].rs].cnt) {
			long long a=tr[tr[tr[i].ls].rs].sum,b=tr[tr[i].ls].sum,c=tr[i].sum;
			long long tp=tr[i].ls;
			tr[i].ls=tr[tp].rs;
			tr[tr[tp].rs].fa=i;
			tr[tp].rs=i;
			if(tr[tr[i].fa].ls==i) {
				tr[tp].fa=tr[i].fa;
				tr[tr[i].fa].ls=tp;
			} else {
				tr[tp].fa=tr[i].fa;
				tr[tr[i].fa].rs=tp;
			}
			tr[i].fa=tp;
			push(i);
			push(tp);
			tr[i].sum=tr[i].sum-b+a;
			tr[tp].sum=c;
		} else {
			if(tr[tr[i].rs].cnt) {
				long long a=tr[tr[tr[i].rs].ls].sum,b=tr[tr[i].rs].sum,c=tr[i].sum;
				long long tp=tr[i].rs;
				tr[i].rs=tr[tp].ls;
				tr[tr[tp].ls].fa=i;
				tr[tp].ls=i;
				if(tr[tr[i].fa].ls==i) {
					tr[tp].fa=tr[i].fa;
					tr[tr[i].fa].ls=tp;
				} else {
					tr[tp].fa=tr[i].fa;
					tr[tr[i].fa].rs=tp;
				}
				tr[i].fa=tp;
				push(i);
				push(tp);
				tr[i].sum=tr[i].sum-b+a;
				tr[tp].sum=c;
			}
		}
	}
}
void insert(long long i,long long val,long long sum) {
	if(val==tr[i].val) {
		tr[i].sum+=sum;
		tr[i].cnt--;
	} else {
		if(val<tr[i].val) {
			if(tr[i].ls==0)
				cnt++,tr[cnt].fa=i,tr[i].ls=cnt,tr[cnt].val=val,tr[cnt].sum=sum,tr[cnt].cnt=1;
			else
				insert(tr[i].ls,val,sum);
		} else {
			if(tr[i].rs==0)
				cnt++,tr[cnt].fa=i,tr[i].rs=cnt,tr[cnt].val=val,tr[cnt].sum=sum,tr[cnt].cnt=1;
			else
				insert(tr[i].rs,val,sum);
		}
	}
	tr[i].sum+=sum;
	tr[i].cnt++;
	if(i!=1)
		rotate(i);
}
long long ans(long long i,long long key) {
	if(tr[i].ls) {
		if(tr[i].rs) {
			if(tr[tr[i].ls].sum>=key) {
				return ans(tr[i].ls,key);
			} else {
				if(tr[i].sum-tr[tr[i].rs].sum>=key)
					return tr[i].val;
				else
					return ans(tr[i].rs,key-(tr[i].sum-tr[tr[i].rs].sum));
			}
		} else {
			if(tr[tr[i].ls].sum>=key)
				return ans(tr[i].ls,key);		
			else
				return tr[i].val; 
		}
	} else {
		if(tr[i].rs) {
			if(tr[i].sum-tr[tr[i].rs].sum>=key)
				return tr[i].val;
			else
				return ans(tr[i].rs,key-(tr[i].sum-tr[tr[i].rs].sum));
		} else {
			return tr[i].val;
		}
	}
}
int main() {
//	freopen("physical.in","r",stdin);
//	freopen("physical.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	long long v,a;
	cin>>v>>a;
	tr[1].val=v,tr[1].sum=a;
	cout<<v<<endl;
	for(long long i=2;i<=n;i++) {
		cin>>v>>a;
		insert(1,v,a);
//		for(int j=1;j<=cnt;j++)
//			cout<<tr[j].fa<<' '<<tr[j].ls<<' '<<tr[j].rs<<' '<<tr[j].val<<' '<<tr[j].sum<<' '<<tr[j].cnt;
		cout<<ans(1,(tr[1].sum/2)+tr[1].sum%2)<<endl; 
	}
	return 0;
}
/*
*/