#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    const int siz=1<<25;
    char a[siz],b[siz],*ia=a+siz,*ea=a+siz,*ib=b,*eb=b+siz;
    int p[105],l=0;
    inline char gc(){if (ia==ea) fread(a,1,siz,stdin),ia=a;return *ia++;}
    inline void flush(){fwrite(b,1,ib-b,stdout);ib=b;}
    inline void pc(char c){if (ib==eb) flush();*ib++=c;}
    inline int read(){
        int x=0;char t=gc();
        for (;t<'0' || t>'9';t=gc());
        for (;'0'<=t && t<='9';t=gc()) x=x*10+t-'0';
        return x;
    }
    inline void write(int x){
        if (!x) pc('0');
        for (;x;x/=10) p[++l]=x%10;
        for (;l;--l) pc(p[l]+'0');pc('\n');
    }
    struct f{~f(){flush();}}F;
}
using IO::read;
using IO::write;
const int N=1e5+5,M=2.5e5+5,B=500;
struct oper{int x,h;}op[M];
int a[N],num[N+M];
int n,m;
void init(){
	n=read(),m=read();
    for (int i=1;i<=n;++i) num[i]=a[i]=read();
    for (int i=1;i<=m;++i) op[i].x=read(),num[n+i]=op[i].h=read();
    sort(num+1,num+1+n+m);num[0]=unique(num+1,num+1+n+m)-num-1;
    for (int i=1;i<=n;++i) a[i]=lower_bound(num+1,num+1+num[0],a[i])-num;
    for (int i=1;i<=m;++i) op[i].h=lower_bound(num+1,num+1+num[0],op[i].h)-num;
    a[0]=a[n+1]=num[0]+1;
}
int bz[N],pre[N];
int st[N],tp;
queue<int> q;
vector<int> son[N];
int siz[N],s[N],dfn[N],rfn[N],top[N],fa[N],tot;
void dfs1(int x){
	siz[x]=1,s[x]=0;
	for (int y:son[x]){
        fa[y]=x;
        dfs1(y);
        siz[x]+=siz[y];
        if (siz[y]>siz[s[x]]) s[x]=y;
    }
}
void dfs2(int x){
    if (!top[x]) top[x]=x;
    rfn[dfn[x]=++tot]=x;
    if (s[x]){
        top[s[x]]=top[x];
        dfs2(s[x]);
    }
    for (int y:son[x])
		if (y!=s[x])
			dfs2(y);
}
int h[4*N],d[4*N],val[4*N],sum[4*N],tag[4*N];
void build(int x,int l,int r){
    tag[x]=sum[x]=0;
    if (l==r){
        if (!bz[rfn[l]]) d[x]=h[x]=a[rfn[l]],val[x]=1;
        else h[x]=d[x]=0,val[x]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    h[x]=max(h[x<<1],h[x<<1|1]);
    d[x]=min(d[x<<1],d[x<<1|1]);
    val[x]=val[x<<1]+val[x<<1|1];
}
void pushdown(int x,int l,int r,int mid){
    sum[x<<1]+=tag[x]*(mid-l+1),tag[x<<1]+=tag[x];
    sum[x<<1|1]+=tag[x]*(r-mid),tag[x<<1|1]+=tag[x];
    tag[x]=0;
}
void pushup(int x){sum[x]=sum[x<<1]+sum[x<<1|1];}
void update(int x,int l,int r,int L,int R,int k,bool fg){
    if (L<=l && r<=R){
        if (h[x]<=k){
            if (fg) sum[x]+=r-l+1,++tag[x];
            else sum[x]-=r-l+1,--tag[x];
            return;
        }
        if (d[x]>k) return;
        int mid=(l+r)>>1;
        pushdown(x,l,r,mid);
        update(x<<1,l,mid,L,R,k,fg);
        update(x<<1|1,mid+1,r,L,R,k,fg);
        pushup(x);
    }
    else{
        int mid=(l+r)>>1;
        pushdown(x,l,r,mid);
        if (L<=mid) update(x<<1,l,mid,L,R,k,fg);
        if (R>mid) update(x<<1|1,mid+1,r,L,R,k,fg);
        pushup(x);
    }
}
int query(int x,int l,int r){
    if (!sum[x]) return val[x];
    if (l==r) return 0;
    int mid=(l+r)>>1;
    pushdown(x,l,r,mid);
    int res=query(x<<1,l,mid)+query(x<<1|1,mid+1,r);
    pushup(x);
    return res;
}
void build(){
    st[tp=1]=0;
    for (int i=0;i<=n+1;++i) pre[i]=fa[i]=0,son[i].clear();
    for (int i=1;i<=n+1;++i){
        if (bz[i]) continue;
        while (a[i]>a[st[tp]]) --tp;
        if (a[st[tp]]==a[i])
			pre[i]=st[tp],--tp;
        st[++tp]=i;
    }
    q.emplace(n+1);
    while (!q.empty()){
        int x=q.front();q.pop();
        for (int i=x-1;i>pre[x];){
        	if (pre[i]){
	            son[x].emplace_back(i);
	            q.emplace(i);
	            i=pre[i];
			}
			else{
            	if (bz[i]) son[x].emplace_back(i);
            	--i;
			}
		}
    }
    for (int i=0;i<=n+1;++i) top[i]=0;
    dfs1(n+1);
    tot=0;dfs2(n+1);
    build(1,1,tot);
}
void modify(int x,int hg,bool fg){
    x=fa[x];
    while (x && a[x]<=hg){
        update(1,1,tot,dfn[top[x]],dfn[x],hg,fg);
        x=fa[top[x]];
    }
}
int firstanswer(){
    int res=0;
    st[tp=1]=0;
    for (int i=1;i<=n+1;++i){
        while (a[i]>a[st[tp]]) --tp;
        if (a[st[tp]]==a[i]) ++res,--tp;
        st[++tp]=i;
    }
    return res-1;
}
struct bp{
    int tp,id,val;
    bp(int x=0,int y=0,int z=0){tp=x,id=y,val=z;}
}c[N],sa[N];
int cnt,w;
int is_pre[B+5][N+M],is_suf[B+5][N+M],Tms=0;
int prepare(int id,int l,int r){
    int res=0;
    for (int i=l,mx=0;i<=r;++i)
        if (a[i]>mx) is_pre[id][res=mx=a[i]]=Tms;
    for (int i=r,mx=0;i>=l;--i)
        if (a[i]>mx) is_suf[id][mx=a[i]]=Tms;
    return res;
}
int calc_to_front(){
    int tp=1,res=0;
    sa[1]=(bp){1,0,num[0]+1};
    for (int i=1;i<=cnt;++i){
        bp t=c[i];
        if (t.tp==1){
            t.val=a[t.val];
            while (t.val>sa[tp].val) --tp;
            if (sa[tp].tp==1) res+=(sa[tp].val==t.val);
            else res+=2*(is_suf[sa[tp].id][t.val]==Tms);
            sa[++tp]=t;
        }
        else{
            while (t.val>sa[tp].val) --tp;
            sa[++tp]=t;
        }
    }
    return res;
}
int calc_to_back(){
    int tp=1,res=0;
    sa[1]=(bp){1,0,num[0]+1};
    for (int i=cnt;i>=1;--i){
        bp t=c[i];
        if (t.tp==1){
            t.val=a[t.val];
            while (t.val>sa[tp].val) --tp;
            if (sa[tp].tp==1) res+=(sa[tp].val==t.val);
            else res+=2*(is_pre[sa[tp].id][t.val]==Tms);
            sa[++tp]=t;
        }
        else{
            while (t.val>sa[tp].val) --tp;
            sa[++tp]=t;
        }
    }
    return res;
}
void work(){
    write(firstanswer());
    for (int k=1;k<=m;k+=B){
    	++Tms;
        for (int i=1;i<=n;++i) bz[i]=0;
        for (int i=k;i<k+B && i<=m;++i) bz[op[i].x]=1;
        build();
        for (int i=1;i<=n;++i) if (bz[i]) modify(i,a[i],0);
        cnt=w=0;
        int lst=0;
        for (int i=1;i<=n;++i)
            if (bz[i]){
                if (lst!=i-1){
                	++w;
                	c[++cnt]=bp(2,w,prepare(w,lst+1,i-1));
				}
                lst=i;
                c[++cnt]=(bp){1,0,i};
            }
        if (lst!=n){
        	++w;
        	c[++cnt]=bp(2,w,prepare(w,lst+1,n));
		}
        for (int i=k;i<k+B && i<=m;++i){
            modify(op[i].x,a[op[i].x],1);
            a[op[i].x]=op[i].h;
            modify(op[i].x,a[op[i].x],0);
            write(query(1,1,tot)-1+(calc_to_front()+calc_to_back())/2);
        }
    }
}
int main(){
    init();
    work();
    return 0;
}