#pragma GCC optimize("Ofast") 
#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 char gc()
{
	static char buf[1<<24],*p1,*p2;
 	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
	char ch=gc();int r=0;
	for(;ch<'0'||ch>'9';ch=gc());
	for(;'0'<=ch&&ch<='9';ch=gc())r=(r<<3)+(r<<1)+(ch-'0');
	return r;
}
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;
int bz1[505][1005],bz2[505][1005],res=0;
unordered_map<int,int> mp;
bool bz[N],viss[N];
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);
		viss[x]|=viss[xx];
		sz[x]+=sz[xx];
		if(sz[xx]>sz[sn[x]])sn[x]=xx;
	}
}
int prr;
void dfs(int x,int tpp)
{
	if(viss[x])po[dfn[x]=++tot]=x;
	else prr++;
	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;
	}
}
cx1 dd[1005];
int d1[N],pos[1005];
void solve(vector<cx1> qs)
{
	tot=prr=0;res++;
	memset(wg,0,sizeof wg);
	memset(he,0,sizeof he);
	memset(bz,0,sizeof bz);
	memset(viss,0,sizeof viss);
	int len=0;
	for(auto xx:qs)if(!bz[xx.x])pos[++len]=xx.x,bz[xx.x]=1;
	sort(pos+1,pos+len+1);
	int bk=0;
	fo(i,1,n)
	if(!bz[i]){
		while(bk&&a[i]>a[d1[bk]])bk--;
		if(bk&&a[i]==a[d1[bk]])
		{
			wg[d1[bk]]=i;
			bk--;
		}
		d1[++bk]=i;
	}
	wg[0]=n+1;
	int t=1;
	id[0]=1;
	num[1]=1000000000;
	d1[bk=1]=0;
	int ctt=0;
	a[qs[0].x]=qs[0].y;
	fo(i,1,n)
	{
		while(wg[d1[bk]]<=i)bk--;
		if(!bz[i])
		{
			if(wg[i])
			{
				id[i]=++t;
				num[t]=a[i];
				lb(id[d1[bk]],id[i]);
				d1[++bk]=i;
			}
		}else sp[i]=id[d1[bk]],viss[id[d1[bk]]]=1;
	}
	dg(1);
	tot=0;
	dfs(1,1);
	build(1,tot,1);
	fo(i,1,len)chg(sp[pos[i]],a[pos[i]],1);
	vector<cx> a1;
	int ls=1,cnt=0;
	pos[++len]=n+1;
	int tot1=0;
	vector<int> pp;
	fo(i,1,len)
	{
		int xx=pos[i];
		if(!mp1[b[xx]])mp1[b[xx]]=++tot1,pp.push_back(b[xx]);
		idd[xx]=mp1[b[xx]];
	}
	for(auto xx:qs)if(!mp1[xx.z])mp1[xx.z]=++tot1,pp.push_back(xx.z);
	fo(i,1,len)
	{
		int yy=pos[i];
		if(ls<yy)
		{
			cnt++;mxx[cnt]=0;
			fo(t,ls,yy-1)mxx[cnt]=max(mxx[cnt],a[t]);
			bj[cnt]={ls,yy-1};
			int bk=0;
			fo(t,ls,yy-1)
			{
				while(bk&&a[t]>=a[d1[bk]])bk--;
				d1[++bk]=t;
			}
			fo(i,1,bk)if(mp1[b[d1[i]]])bz1[cnt][mp1[b[d1[i]]]]=res;
			bk--;
			fd(t,yy-1,ls)
			{
				while(bk&&a[t]>=a[d1[bk]])bk--;
				d1[++bk]=t;
			}
			fo(i,1,bk)if(mp1[b[d1[i]]])bz2[cnt][mp1[b[d1[i]]]]=res;
			bk--;
		}
		ls=yy+1;
	}
	len--;
	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=prr,wz=0,bk=0;
		if(!tr[1])ans+=ct[1]-1;
		pos[++len]=n+1;
		fo(i,1,len)
		{
			int xx=pos[i];
			if(bj[wz+1].y<xx&&wz<cnt)
			{
				wz++;
				while(bk&&mxx[wz]>=dd[bk].z)
				{
					if(!dd[bk].y)ans+=(bz2[wz][dd[bk].x]==res);
					bk--;
				}
				dd[++bk]={wz,1,mxx[wz]};
			}
			if(xx==n+1)break;
			while(bk&&a[xx]>dd[bk].z)bk--;
			if(bk&&dd[bk].z>=a[xx])
			{
				if(!dd[bk].y)ans+=(dd[bk].z==a[xx]);
				else ans+=(bz1[dd[bk].x][idd[xx]]==res);
				if(dd[bk].z==a[xx])bk--;
			}
			dd[++bk]={idd[xx],0,a[xx]};
		}
		len--;
		write(ans);
	}
	for(auto xx:pp)mp1[xx]=0;
	cnt=0;
}
int main()
{
	n=read();
	int m=read();
	fo(i,1,n)
	{
		a[i]=read();
		if(!mp[a[i]])mp[a[i]]=++cut,b[i]=cut;
		else b[i]=mp[a[i]];
	}
	cal();
	vector<cx1> qs;
	while(m--)
	{
		int x=read(),y=read();
		if(!mp[y])mp[y]=++cut,qs.push_back({x,y,cut});
		else qs.push_back({x,y,mp[y]}); 
		if(qs.size()==400)solve(qs),qs.clear();
	}
	if(!qs.empty())solve(qs);
	return 0;
}