ll@n,@q,@a[n],@(i,x,l,r)[q];
fenwick<ll>fi,fs;
fi.malloc(n+q,1);
fs.malloc(n+q,1);
rrep(j,n+q){
	fi.add(j,1);
}
rrep(j,q){
	r[j]=fi.kth(r[j]-1);
	l[j]=fi.kth(l[j]-1);
	i[j]=fi.kth(i[j]);
	fi.add(i[j],-1);
}
rep(j,n){
	fs.add(fi.kth(j),a[j]);
}
rep(j,q){
	fs.add(i[j],x[j]);
	wt(fs.range(l[j],r[j]));
}