fenwick<ll>fi,fs;
ll kth(ll v){
	ll k=-1,d=1<<16;
	while(d){
		if(fi.data[k+d]<=v){
			v-=fi.data[k+d];
			k+=d;
		}else{
		}
		d>>=1;
	}
	return k+1;
}
{
	ll@n,@q,@a[n],@(i,x,l,r)[q];
	fi.malloc(1<<17,1);
	fs.malloc(n+q,1);
	rrep(j,n+q){
		fi.add(j,1);
	}
	rrep(j,q){
		r[j]=kth(r[j]-1);
		l[j]=kth(l[j]-1);
		i[j]=kth(i[j]);
		fi.add(i[j],-1);
	}
	rep(j,n){
		fs.add(kth(j),a[j]);
	}
	rep(j,q){
		fs.add(i[j],x[j]);
		wt(fs.range(l[j],r[j]));
	}
}