#include<bits/stdc++.h>
#define N 100000
#define Q 250000
using namespace std;
const int B=350;
namespace IO
{
    const int SIZE=1<<21;
    char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;
    #define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
    inline void flush()
    {
        fwrite(obuf,1,oS-obuf,stdout);
        oS=obuf;
    }
    inline void putc(char x)
    {
        *oS++=x;
        if(oS==oT) flush();
    }
    template<class I>
    inline void read(I &x)
    {
        for(f=1,c=gc();c<'0' || c>'9';c=gc()) if(c=='-') f=-1;
        for(x=0;c<='9' && c>='0';c=gc()){x=(x<<1)+(x<<3)+(c&15);}x*=f;
    }
    template<class I>
    inline void print(I x)
    {
        if(!x) putc('0');
        if(x<0) putc('-'),x=-x;
        while(x) qu[++qr]=x%10+'0',x/=10;
        while(qr) putc(qu[qr--]);
    }
    struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::putc;
using IO::print;
int n,q,a[N+5],x[Q+5],h[Q+5],v[N+Q+5],cnt,pre[N+5],nxt[N+5],Fa[N+5];
set<int> s[N+Q+5];
vector<int> e[N+5];
bool vis[N+5];
int root[N+5],tot,p[N+5],siz[N+5],dfn[N+5],son[N+5],fa[N+5],Top[N+5],idfn[N+5],Ans;
int Nxt2[B+5],Pre2[B+5],Pre[B+5],Nxt[B+5],Pre1[B+5],Nxt1[B+5],npre[N+5],id[N+5],node[B+5],val[B+5];
inline void merge(int u,int v)
{
	if(!u) root[++root[0]]=v;
	siz[u]+=siz[v],e[u].push_back(v),Fa[v]=u;
	if(siz[v]>siz[son[u]]) son[u]=v;
}
inline void dfs(int x)
{
	idfn[dfn[x]=++cnt]=x;
	if(son[x]) Top[son[x]]=Top[x],dfs(son[x]);
	for(int y:e[x]) if(y!=son[x]) Top[y]=y,dfs(y);
}
namespace SGT
{
	#define mid ((l+r)>>1)
	#define lson x<<1
	#define rson x<<1|1
	int t[N*4+5],tag[N*4+5];
	inline void push_up(int x,int l,int r)
	{
		if(tag[x]) return t[x]=0,void();
		t[x]=(l==r?1:(t[lson]+t[rson]));
	}
	inline void build(int x,int l,int r)
	{
		t[x]=r-l+1,tag[x]=0;if(l==r) return;
		build(lson,l,mid),build(rson,mid+1,r);
	}
	inline void update(int x,int l,int r,int le,int ri,int v)
	{
		if(le>ri || l>ri || r<le) return;
		if(le<=l && r<=ri) return tag[x]+=v,push_up(x,l,r);
		update(lson,l,mid,le,ri,v),update(rson,mid+1,r,le,ri,v),push_up(x,l,r);
	}
}
namespace SGT2
{
	int t[N*4+5];
	inline void insert(int x,int l,int r,int p,int v)
	{
		if(l==r) return t[x]=v,void();
		p<=mid?insert(lson,l,mid,p,v):insert(rson,mid+1,r,p,v);
		t[x]=max(t[lson],t[rson]); 
	}
	inline int queryl(int x,int l,int r,int p,int v)
	{
		if(l>=p || t[x]<v) return 0;
		if(l==r) return l;
		int rans=queryl(rson,mid+1,r,p,v);
		return rans?rans:queryl(lson,l,mid,p,v);
	}
	inline int queryr(int x,int l,int r,int p,int v)
	{
		if(r<=p || t[x]<v) return n+1;
		if(l==r) return l;
		int lans=queryr(lson,l,mid,p,v);
		return lans!=n+1?lans:queryr(rson,mid+1,r,p,v);
	}
}
using SGT::build;
using SGT::update;
inline void modify(int x,int up,int v)
{
	for(;x && a[p[Top[x]]]<=up;x=Fa[Top[x]])
		update(1,1,tot,dfn[Top[x]],dfn[x],v);
	if(!x) return;
	int l=dfn[Top[x]]+1,r=dfn[x]+1;
	while(l<r) a[p[idfn[mid]]]<=up?r=mid:l=mid+1;
	update(1,1,tot,l,dfn[x],v);
}
#undef mid
inline void update(int x)
{
	Pre[id[x]]=SGT2::queryl(1,1,n,x,a[x]);
	Nxt[id[x]]=SGT2::queryr(1,1,n,x,a[x]);
}
inline void Update(int x)
{
	if(vis[x]) Pre2[id[x]]=pre[x],Nxt2[id[x]]=nxt[x];
}
inline void change(int x,int h)
{
	set<int>::iterator it=s[a[x]].find(x);
	pre[nxt[*prev(it)]=*next(it)]=*prev(it);
	Update(*prev(it)),Update(*next(it));
	modify(fa[x],a[x],-1),s[a[x]].erase(it);
	modify(fa[x],a[x]=h,1),it=s[a[x]].insert(x).first;
	pre[nxt[x]=*next(it)]=x,nxt[pre[x]=*prev(it)]=x;
	Update(*prev(it)),Update(x),Update(*next(it));
}
inline void getans()
{
	static int st[N+5],top;
	int ans=Ans+SGT::t[1];
	st[top=0]=0;
	for(int i=1;i<=node[0];++i)
	{
		while(top && val[i]>val[st[top]]) --top;
		Pre1[i]=top?node[st[top]]:0;st[++top]=i;
	}
	st[top=0]=n+1;
	for(int i=node[0];i;--i)
	{
		while(top && val[i]>val[st[top]]) --top;
		Nxt1[i]=top?node[st[top]]:n+1;st[++top]=i;
	}
	for(int i=1;i<=node[0];++i)
	{
		if(Nxt2[i]!=n+1 && Nxt[i]>=Nxt2[i] && Nxt1[i]>=Nxt2[i]) ++ans;
		if(Pre2[i] && !vis[Pre2[i]] && Pre[i]<=Pre2[i] && Pre1[i]<=Pre2[i]) ++ans;
	}
	print(ans),putc('\n');
}
inline void solve(int l,int r)
{
	static bool ok[N+5];
	static int st[N+5],top,s[N+5];
	for(int i=l;i<=r;++i) vis[x[i]]=1;
	node[0]=0,st[top=0]=0;
	for(int i=1;i<=n;++i)
	{
		s[i]=s[i-1],ok[i]=0;
		if(!vis[i])
		{
			while(top && a[i]>a[st[top]]) --top;
			if(a[i]==a[st[top]]) ok[i]=1,npre[i]=st[top];
			st[++top]=i;
		}
		else ++s[i],node[++node[0]]=i,id[i]=node[0];
	}
	top=0,tot=0,Ans=0,root[0]=0;
	for(int i=n;i;--i) if(vis[i] || ok[i])
	{
		for(;top && npre[p[st[top]]]>=i;--top)
			merge(st[top-1],st[top]);
		if(vis[i]) fa[i]=st[top];
		else if(s[i]-s[npre[i]])
			p[st[++top]=++tot]=i,siz[tot]=1,son[tot]=0,e[tot].clear();
		else ++Ans;
	}
	for(;top;--top) merge(st[top-1],st[top]);
	cnt=0;for(int i=1;i<=root[0];++i) Top[root[i]]=root[i],dfs(root[i]);
	if(tot) build(1,1,tot);
	else SGT::t[1]=0;
	for(int i=1;i<=node[0];++i) SGT2::insert(1,1,n,node[i],0);
	for(int i=1;i<=node[0];++i)
	{
		update(node[i]),Update(node[i]);
		val[id[node[i]]]=a[node[i]];
	}
	for(int i=1;i<=node[0];++i) modify(fa[node[i]],val[i],1);
	if(l==1) getans();
	for(int i=l;i<=r;++i)
	{
		change(x[i],h[i]);
		update(x[i]);
		val[id[x[i]]]=h[i];
		getans();
	}
	for(int i=1;i<=node[0];++i) SGT2::insert(1,1,n,node[i],val[i]);
	for(int i=l;i<=r;++i) vis[x[i]]=0;
}
int main()
{
	read(n),read(q);
	for(int i=1;i<=n;++i) read(a[i]),v[++cnt]=a[i];
	for(int i=1;i<=q;++i) read(x[i]),read(h[i]),v[++cnt]=h[i];
	sort(v+1,v+1+cnt),cnt=unique(v+1,v+1+cnt)-v-1;
	for(int i=0;i<=cnt;++i) s[i].insert(0),s[i].insert(n+1);
	for(int i=1;i<=n;++i) a[i]=lower_bound(v+1,v+1+cnt,a[i])-v;
	for(int i=1;i<=q;++i) h[i]=lower_bound(v+1,v+1+cnt,h[i])-v;
	for(int i=1,h;i<=n;++i) h=a[i],s[a[i]=0].insert(i),change(i,h),SGT2::insert(1,1,n,i,h);
	for(int i=1;i<=q;i+=B) solve(i,min(q,i+B-1));
	return 0;
}