#include<bits/stdc++.h>
using namespace std;
#define double long double
#define lowbit(x) (x&(-x))
int ls[14000005],rs[14000005],sum[14000005];
#define int long long
int val[14000005];
int nw =1;
void update(int k,int pos,int add1,int add2,int l,int r){
	if(l+1 == r){
		sum[k]+=add1;
		val[k]+=add2;
		return;
	}
	int mid = l+r>>1;
	if(pos<mid){
		if(!ls[k])ls[k] = ++nw;
		update(ls[k],pos,add1,add2,l,mid);
	}else{
		if(!rs[k])rs[k] = ++nw;
		update(rs[k],pos,add1,add2,mid,r);
	}
	sum[k]=sum[ls[k]]+sum[rs[k]];
	val[k]=val[ls[k]]+val[rs[k]];
//	cout << " " <<  k << " " << l << " " << r << " " << sum[k] << " " << val[k] << endl;
}
int find(int k,int l,int r,int x){
//	cout << k << " " << l << " " << r << " " << x << endl;
	if(!k)return 0;
	if(l+1 == r){return min(x/l,val[k]);}
	if(sum[ls[k]]>=x)return find(ls[k],l,l+r>>1,x);
	return find(rs[k],l+r>>1,r,x-sum[ls[k]])+val[ls[k]];
}
int query(int k,int l,int r,int ll,int rr){
	if(!k or l>=rr or ll>=r)return 0;
	if(l<=ll and rr<=r)return val[k];
	return query(ls[k],l,r,ll,ll+rr>>1)+query(rs[k],l,r,ll+rr>>1,rr);
}

const int M = 1000000001;
int ssum = 0,tot = 0;
int a[500005];
int n,q;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for(int i = 1;i<=n;i++)cin >> a[i];
	for(int i = 1;i<=n;i++){
		if(a[i]<0){
			ssum+=-a[i];
		}else{
			++tot;
			update(1,a[i],a[i],1,1,M+1);
		}
	}
	for(int i = 1;i<=q;i++){
		int pos,v;cin >> pos >> v;
		if(a[pos]<0){
			ssum-=-a[pos];
		}
		if(a[pos]>0){
			--tot;
			update(1,a[pos],-a[pos],-1,1,M+1);
		}
		if(v<0){
			ssum+=-v;
		}
		if(v>0){
			++tot;
			update(1,v,v,1,1,M+1);
		}
		a[pos] = v;
		int x = find(1,1,M+1,ssum)+1;
		cout << x << '\n';
	} 
	return 0;
}/*
3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1
*/