纯良树状数组代码求条qwq

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) x&(-x)
using namespace std;
long long n,a[100005],f[100005],tr[100005],maxx;
map<int,int>M;
inline void init(){
	for(int i=1;i<=n;i++){
		f[i]=a[i];
	}
	sort(f+1,f+1+n);
	int cnt=unique(f+1,f+1+n)-f-1;
	for(int i=1;i<=n;i++){
		int qwq=a[i];
		a[i]=lower_bound(f+1,f+1+cnt,a[i])-f;
		M[a[i]]=qwq;
		maxx=max(maxx,a[i]);
	}
	return;
}
inline void add(int x){
	for(int i=x;i<=maxx;i+=lowbit(i)){
		tr[i]++;
	}
	return;
}
inline int sum(int x){
	int qwq=0;
	for(int i=x;i>0;i-=lowbit(i)){
		qwq+=tr[i];
	}
	return qwq;
}
inline int query(int l,int r){
	return sum(r)-sum(l-1);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	init();
	for(int i=1;i<=n;i++){
		add(a[i]);
		if(i%2==1){
//			for(int j=1;j<=i;j++){
//				if(query(a[j]+1,maxx)==i/2){
//					cout<<M[a[j]]<<endl;
//					break;
//				}
//			}
			int l=1,r=i,vis=0;
			while(l<=r){
				int mid=(l+r)/2;
				int qwq=query(a[mid]+1,maxx);
				if(qwq==i/2){
					cout<<M[a[mid]]<<endl;
					vis=1;
					break;
				}
				if(query(a[mid]+1,maxx)<i/2){
					l=mid+1;
				}
				else{
					r=mid;
				}
			}
			if(!vis){
				cout<<M[a[l]]<<endl;
			}
		}
	}
	return 0;
}