#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
inline int read()
{
	int X=0,w=0;char ch=0;
	while(!isdigit(ch))w|=ch=='-',ch=getchar();
	while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
	return w?-X:X;
}
namespace IO{
	const int sz=1<<23;
	char b[sz+5],*t=b,p[15];
	inline void flush(){fwrite(b,1,t-b,stdout),t=b;}
	inline void pc(char x){*t++=x;if(t-b==sz)flush();}
	template<class T>void write(T x,char c='\n'){
		if(x==0)pc('0');int t=0;
		for(;x;x/=10)p[++t]=x%10+'0';
		for(;t;--t)pc(p[t]);pc(c);
	}
	struct F{~F(){flush();}}f;
}
using IO::write;
#define k1 (k<<1)
#define k2 (k1+1)
#define N 100005
struct cx{
	int x,y;
}bj[N];
struct cx1{
	int x,y,z;
};
int he[N],la[N],ne[N],tot=0,a[N],n,tr[N<<2],ad[N<<2],ct[N<<2],mn[N<<2],mx[N<<2],mp1[350005];
int sz[N],sn[N],dfn[N],po[N],tp[N],num[N],fa[N],wg[N],id[N],sp[N],mxx[2005],idd[N],b[N],cut=0;
bool bz1[2005][2005],bz2[1005][2005];
map<int,int> mp;
bool bz[N];
vector<int> d1[2005],d2[2005];
void cal()
{
	int ct=0;
	vector<int> d;
	fo(i,1,n)
	{
		while(!d.empty()&&a[i]>a[d.back()])d.pop_back();
		if(!d.empty()&&a[i]==a[d.back()])
		{
			ct++;
			d.pop_back();
		}
		d.push_back(i);
	}
	printf("%d\n",ct);
}
void lb(int x,int y)
{
	ne[++tot]=he[x];
	la[he[x]=tot]=y;
	fa[y]=x;
}
void dg(int x)
{
	sz[x]=1;sn[x]=0;
	for(int ii=he[x];ii;ii=ne[ii])
	{
		int xx=la[ii];
		dg(xx);
		sz[x]+=sz[xx];
		if(sz[xx]>sz[sn[x]])sn[x]=xx;
	}
}
void dfs(int x,int tpp)
{
	po[dfn[x]=++tot]=x;
	tp[x]=tpp;
	if(sn[x])dfs(sn[x],tpp);
	for(int ii=he[x];ii;ii=ne[ii])
	{
		int xx=la[ii];
		if(xx!=sn[x])dfs(xx,xx);
	}
}
void build(int l,int r,int k)
{
	tr[k]=ad[k]=0;
	ct[k]=r-l+1;
	if(l==r)
	{
		mx[k]=mn[k]=num[po[l]];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,k1);
	build(mid+1,r,k2);
	mn[k]=min(mn[k1],mn[k2]);
	mx[k]=max(mx[k1],mx[k2]);
}
void pushdown(int k)
{
	if(ad[k])
	{
		ad[k1]+=ad[k];
		tr[k1]+=ad[k];
		ad[k2]+=ad[k];
		tr[k2]+=ad[k];
		ad[k]=0;
		return;
	}
}
void modify(int l,int r,int k,int x,int y,int v1,int v2)
{
	if(mn[k]>v1)return;
	if(l>=x&&r<=y&&mx[k]<=v1)
	{
		ad[k]+=v2;
		tr[k]+=v2;
		return;
	}
	int mid=l+r>>1; 
	pushdown(k);
	if(mid>=x)modify(l,mid,k1,x,y,v1,v2);
	if(mid<y)modify(mid+1,r,k2,x,y,v1,v2);
	tr[k]=min(tr[k1],tr[k2]);
	ct[k]=(tr[k1]==tr[k])*ct[k1]+(tr[k2]==tr[k])*ct[k2];
}
void chg(int x,int y,int v)
{
	while(x)
	{
		int tpp=tp[x];
		modify(1,tot,1,dfn[tpp],dfn[x],y,v);
		if(num[tpp]<y)x=fa[tpp];
		else break;
	}
}
void solve(vector<cx> qs)
{
	tot=0;
	memset(wg,0,sizeof wg);
	memset(he,0,sizeof he); 
	memset(bz,0,sizeof bz);
	vector<int> pos;
	for(auto xx:qs)if(!bz[xx.x])pos.push_back(xx.x),bz[xx.x]=1;
	sort(pos.begin(),pos.end());
	vector<int> d;
	fo(i,1,n)
	if(!bz[i]){
		while(!d.empty()&&a[i]>a[d.back()])d.pop_back();
		if(!d.empty()&&a[i]==a[d.back()])
		{
			wg[d.back()]=i;
			d.pop_back();
		}
		d.push_back(i);
	}
	d.clear();
	wg[0]=n+1;
	int t=1;
	id[0]=1;
	num[1]=1000000000;
	d.push_back(0);
	int ctt=0;
	a[qs[0].x]=qs[0].y;
	fo(i,1,n)
	{
		while(wg[d.back()]<=i)d.pop_back();
		if(!bz[i])
		{
			if(wg[i])
			{
				id[i]=++t;
				num[t]=a[i];
				lb(id[d.back()],id[i]);
				d.push_back(i);
			}
		}else sp[i]=id[d.back()],ctt+=(a[i]>=num[sp[i]]);
	}
	dg(1);
	tot=0;
	dfs(1,1);
	build(1,tot,1);
	for(auto xx:pos)chg(sp[xx],a[xx],1);
	vector<cx> a1;
	int ls=1,cnt=0;
	pos.push_back(n+1);
	int tot1=0;
	vector<int> pp;
	for(auto xx:pos)if(!mp1[b[xx]])mp1[b[xx]]=++tot1,pp.push_back(b[xx]);
	for(auto xx:pos)idd[xx]=mp1[b[xx]];
	for(auto xx:qs)if(!mp1[mp[xx.y]])mp1[mp[xx.y]]=++tot1,pp.push_back(mp[xx.y]);
	for(auto yy:pos)
	{
		if(ls<yy)
		{
			cnt++;mxx[cnt]=0;
			d1[cnt].clear();d2[cnt].clear();
			fo(t,ls,yy-1)mxx[cnt]=max(mxx[cnt],a[t]);
			bj[cnt]={ls,yy-1};
			vector<int> d;
			fo(t,ls,yy-1)
			{
				while(!d.empty()&&a[t]>=a[d.back()])d.pop_back();
				d.push_back(t);
			}
			for(auto xx:d)if(mp1[b[xx]])d1[cnt].push_back(mp1[b[xx]]);
			for(auto xx:d1[cnt])bz1[cnt][xx]=1;
			d.clear();
			fd(t,yy-1,ls)
			{
				while(!d.empty()&&a[t]>=a[d.back()])d.pop_back();
				d.push_back(t); 
			}
			for(auto xx:d)if(mp1[b[xx]])d2[cnt].push_back(mp1[b[xx]]);
			for(auto xx:d2[cnt])bz2[cnt][xx]=1;
		}
		ls=yy+1;
	}
	pos.pop_back();
	for(auto xx:qs)
	{
		chg(sp[xx.x],a[xx.x],-1);
		chg(sp[xx.x],a[xx.x]=xx.y,1);
		b[xx.x]=mp[xx.y];
		idd[xx.x]=mp1[b[xx.x]];
		int ans=0;
		if(!tr[1])ans=ct[1]-1;
		int wz=0;
		vector<cx1> d;
		pos.push_back(n+1);
		for(auto xx:pos)
		{
			if(bj[wz+1].y<xx&&wz<cnt)
			{
				wz++;
				while(!d.empty()&&mxx[wz]>=d.back().z)
				{
					if(!d.back().y)ans+=bz2[wz][d.back().x];
					d.pop_back();
				}
				d.push_back({wz,1,mxx[wz]});
			}
			if(xx==n+1)break;
			while(!d.empty()&&a[xx]>d.back().z)d.pop_back();
			if(!d.empty()&&d.back().z>=a[xx])
			{
				if(!d.back().y)ans+=(d.back().z==a[xx]);
				else ans+=bz1[d.back().x][idd[xx]];
				if(d.back().z==a[xx])d.pop_back();
			}
			d.push_back({idd[xx],0,a[xx]});
		}
		pos.pop_back();
		write(ans);
	}
	for(auto xx:pp)mp1[xx]=0;
	fo(i,1,cnt)
	{
		for(auto xx:d1[i])bz1[i][xx]=0;
		for(auto xx:d2[i])bz2[i][xx]=0;
		d1[i].clear();d2[i].clear();
	}
	cnt=0;
}
bool vis[N];
int main()
{
	n=read();
	int m=read();
	fo(i,1,n)
	{
		a[i]=read();
		if(!mp[a[i]])mp[a[i]]=++cut;
		b[i]=mp[a[i]];
	}
	cal();
	vector<cx> qs;
	int szz=0;
	while(m--)
	{
		int x=read(),y=read();
		if(!mp[y])mp[y]=++cut;
		if(!vis[x])
		{
			vis[x]=1;
			szz++;
		}
		qs.push_back({x,y});
		if(qs.size()==350)solve(qs),qs.clear();
	}
	if(!qs.empty())solve(qs);
	return 0;
}