#include <bits/stdc++.h>
using namespace std;
int n,h[200005],root;
struct t1
{
	int fa,s[2];
	int va,size;
	long long sum;
	t1()
	{
		fa=s[0]=s[1]=0;
		va=size=sum=0;
	}
}t[200005];
bool get(int x)
{
	return x==t[t[x].fa].s[1];
}
void maintain(int x)
{
	t[x].sum=t[t[x].s[0]].sum+t[t[x].s[1]].sum+t[x].va;
	t[x].size=t[t[x].s[0]].size+t[t[x].s[1]].size+1;
}
void rotate(int x)
{
	int y=t[x].fa,z=t[y].fa,opt=get(x);
	t[y].s[opt]=t[x].s[opt^1];
	if(t[x].s[opt^1])
	{
		t[t[x].s[opt^1]].fa=y;
	}
	t[x].s[opt^1]=y;
	t[y].fa=x;
	t[x].fa=z;
	if(z)
	{
		t[z].s[y==t[z].s[1]]=x;
	}
	maintain(y);
	maintain(x);
}
void update(int x)
{
//	cout<<"update"<<x<<endl;
	maintain(x);
	if(t[x].fa)
	{
		update(t[x].fa);
	}
}
void Splay(int x,int k)
{
	update(x);
	while(t[x].fa!=k)
	{
		int y=t[x].fa,z=t[y].fa;
		if(z!=k)
		{
			if(get(x)==get(y))
			{
				rotate(y);
			}
			else
			{
				rotate(x);
			}
		}
		rotate(x);
	}
	if(!k)
	{
		root=x;
	}
}
void output(int p)
{
	if(!p)
	{
		return;
	}
	output(t[p].s[0]);
	cout<<" "<<t[p].va;
	output(t[p].s[1]);
}
int rnk(int p,int va)
{
	if(t[t[p].s[0]].size==va-1)
	{
		return p;
	}
	else if(t[t[p].s[0]].size<va-1)
	{
		return rnk(t[p].s[1],va-t[t[p].s[0]].size-1);
	}
	else
	{
		return rnk(t[p].s[0],va);
	}
}
int ask(int p)
{
	Splay(rnk(root,1),0);
	Splay(rnk(root,p+2),rnk(root,1));
//	output(t[p+2].s[0]);
//	cout<<endl;
//	cout<<t[t[p+2].s[0]].sum<<"!!!"<<endl;
	return t[t[rnk(root,p+2)].s[0]].sum;
}
void insert(int x)
{
	int p=root;
	while(p)
	{
//		cout<<p<<endl;
		if(t[x].va>t[p].va)
		{
			if(!t[p].s[1])
			{
				t[p].s[1]=x;
				t[x].fa=p;
			//	cout<<"update"<<x<<endl;
		//		exit(0);
				Splay(x,0);
				return;
			}
			p=t[p].s[1];
		}
		else
		{
			if(!t[p].s[0])
			{
				t[p].s[0]=x;
				t[x].fa=p;
			//	cout<<"update"<<x<<endl;
			//	cout<<t[2].fa<<" "<<t[t[2].fa].fa<<" "<<t[t[t[2].fa].fa].fa<<endl;
			//	exit(0);
				Splay(x,0);
				return;
			}
			p=t[p].s[0];
		}
	}
}
int nxt(int p)
{
	while(t[p].s[1])
	{
		p=t[p].s[1];
	}
	return p;
}
void erase(int p)
{
	Splay(p,0);
	if(!t[p].s[0])
	{
		t[t[p].s[1]].fa=t[p].fa;
		if(t[p].fa)
		{
			t[t[p].fa].s[get(p)]=t[p].s[1]; 
		}
		Splay(t[p].s[1],0);
	}
	else if(!t[p].s[1])
	{
		t[t[p].s[0]].fa=t[p].fa;
		if(t[p].fa)
		{
			t[t[p].fa].s[get(p)]=t[p].s[0];
		}
		Splay(t[p].s[0],0);
	}
	else
	{
		int v=nxt(t[p].s[0]);
	//	cout<<v<<endl;
		Splay(v,p);
		t[v].s[1]=t[p].s[1]; 
		t[t[p].s[1]].fa=v;
		t[v].fa=t[p].fa;
		if(t[p].fa)
		{
			t[t[p].fa].s[get(p)]=v;
		}
		Splay(v,0);
	}
	t[p].fa=t[p].s[0]=t[p].s[1]=0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q,maxn=0;
	cin>>n>>q;
	t[1].va=INT_MIN;
	t[n+2].va=INT_MAX;
	t[1].s[1]=n+2;
	t[n+2].fa=1;
	maintain(n+2);
	maintain(1);
	root=1;
	h[1]=1;
	for(int i=2;i<=n+1;i++)
	{
		cin>>t[i].va;
		insert(i);
		h[i]=i;
		maxn+=(t[i].va>0);
	}
	auto check=[](int p)
	{
		return ask(p)<=0;	
	};
	for(int j=1;j<=n;j++)
	{
//		cout<<ask(j)<<endl;
	}
//	cout<<endl;
	for(int i=1;i<=q;i++)
	{
	//	output(root);
	//	cout<<"!"<<endl;
		int x,v;
		cin>>x>>v;
		maxn-=(t[x+1].va>0);
		maxn+=(v>0);
		t[x+1].va=v;
	//	cout<<"erase"<<x+1<<" "<<t[4].fa<<endl;
		erase(x+1);
	//	cout<<t[4].fa<<" "<<t[5].fa<<endl;
	//	cout<<"insert"<<x+1<<endl;
		insert(x+1);
		for(int j=1;j<=n;j++)
		{
//			cout<<ask(j)<<" ";
		}
//		cout<<endl;
		int p=partition_point(h+1,h+n+1,check)-h;
		int minn=n+1-p;
//		cout<<p<<"\n";
		cout<<maxn-minn+1<<"\n"; 
//		cout<<maxn<<" "<<minn<<"\n";
//		cout<<"---"<<endl;
	}
	return 0;
}
/*
4 7
3 -1 2 3
1 1
2 3
3 -10
4 -5
1 2
2 10
3 1
ans: 2 1 4 3 3 3 3

4 7
3 5 -10 10
3 -11
1 5
2 -3
1 -1
4 -5
1 1
2 3
ans: 3 3 2 2 1 2 3

3 2
-1 -2 -3
1 1
2 1
ans:2 3

4 3
1 5 -2 4
3 0
2 -5
1 0
ans:3 3 2

2 2
0 0 
1 0
2 0
ans:0 0
*/