#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=1e5+5,M=2.5e5+5,INF=1e9;
int n,q,a[N],A[N],pos[M],rp[M],b[N+M],ans[M],bns[M];
set<int>pre[N+M],suf[N+M];
vector<tuple<int,int,int,int>>vec[N+M];
struct node{int mxa,sea,mxb,seb,adc;}T[M*4];
inline void pushup(const int&p){
    const int ls=p*2,rs=p*2+1;
    T[p].mxa=max(T[ls].mxa,T[rs].mxa);
    T[p].mxb=max(T[ls].mxb,T[rs].mxb);
    T[p].sea=max((T[p].mxa==T[ls].mxa?T[ls].sea:T[ls].mxa),(T[p].mxa==T[rs].mxa?T[rs].sea:T[rs].mxa));
    T[p].seb=max((T[p].mxb==T[ls].mxb?T[ls].seb:T[ls].mxb),(T[p].mxb==T[rs].mxb?T[rs].seb:T[rs].mxb));
    T[p].adc=0;
}
inline void build(int p,int l,int r,int a,int b){
    T[p].mxa=a,T[p].sea=-1-INF,T[p].mxb=b,T[p].seb=-1-INF,T[p].adc=0;
    if(l==r)return;
    const int mid=(l+r)>>1;
    build(p*2,l,mid,a,b),build(p*2+1,mid+1,r,a,b);
}
inline void upd(int p,int l,int r,int a,int b,int c){
    if(T[p].mxa<a||T[p].mxb<b){
        T[p].mxa=min(T[p].mxa,a),T[p].mxb=min(T[p].mxb,b);
        return;
    }
    if(T[p].sea<a&&T[p].seb<b){
        T[p].mxa=min(T[p].mxa,a),T[p].mxb=min(T[p].mxb,b),T[p].adc+=c;
        return;
    }
    const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
    upd(ls,l,mid,T[p].mxa,T[p].mxb,T[p].adc);
    upd(rs,mid+1,r,T[p].mxa,T[p].mxb,T[p].adc);
    upd(ls,l,mid,a,b,c);
    upd(rs,mid+1,r,a,b,c);
    pushup(p);
}
inline void upd(int p,int l,int r,int x,int y,int a,int b,int c){
    if(x<=l&&r<=y)return upd(p,l,r,a,b,c);
    const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
    upd(ls,l,mid,T[p].mxa,T[p].mxb,T[p].adc);
    upd(rs,mid+1,r,T[p].mxa,T[p].mxb,T[p].adc);
    if(x<=mid)upd(ls,l,mid,x,y,a,b,c);
    if(mid<y)upd(rs,mid+1,r,x,y,a,b,c);
    pushup(p);
}
inline void qry(int p,int l,int r){
    if(l==r)return bns[l]=T[p].adc,void();
    const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
    upd(ls,l,mid,T[p].mxa,T[p].mxb,T[p].adc);
    upd(rs,mid+1,r,T[p].mxa,T[p].mxb,T[p].adc);
    qry(ls,l,mid),qry(rs,mid+1,r);
}
inline void solve(int l,int r,vector<tuple<int,int,int>>&Q){
    if(l>=r)return;
    const int mid=(l+r)>>1;
    int m=r-l+1,q=0;
    copy(a+l,a+r+1,b+1);
    vector<tuple<int,int,int>>nQ;
    for(auto&[x,y,id]:Q)if(l<=x&&x<=r)
        nQ.emplace_back(x,y,id),b[++m]=y,rp[pos[id]=++q]=id;
    sort(b+1,b+m+1);
    for(int i=l;i<=r;++i)
        A[i]=lower_bound(b+1,b+m+1,a[i])-b,
        (i<=mid?pre[A[i]]:suf[A[i]]).emplace(i<=mid?-i:i);
    for(int i=1;i<=m;++i)
        vec[i].emplace_back(
            0,q,
            pre[i].empty()?INF:*pre[i].begin(),
            suf[i].empty()?INF:*suf[i].begin());
    for(auto [x,y,id]:nQ){
        y=lower_bound(b+1,b+m+1,y)-b;
        int z=A[x];
        if(y!=z){
            get<1>(vec[y].back())=pos[id]-1;
            get<1>(vec[z].back())=pos[id]-1;
            if(x<=mid)pre[z].erase(-x),pre[y].emplace(-x);
            else suf[z].erase(x),suf[y].emplace(x);
            A[x]=y;
            vec[y].emplace_back(
                pos[id],q,
                pre[y].empty()?INF:*pre[y].begin(),
                suf[y].empty()?INF:*suf[y].begin());
            vec[z].emplace_back(
                pos[id],q,
                pre[z].empty()?INF:*pre[z].begin(),
                suf[z].empty()?INF:*suf[z].begin());
        }
    }
    build(1,0,q,-l,r);
    for(int i=m;i>=1;--i){
        for(auto [l,r,x,y]:vec[i])upd(1,0,q,l,r,x,y,1);
        pre[i].clear(),suf[i].clear(),vec[i].clear();
    }
    qry(1,0,q);
    for(int i=0;i<=q;++i)ans[rp[i]]+=bns[i]-(i?bns[i-1]:0);
    Q=nQ,solve(l,mid,Q),solve(mid+1,r,nQ);
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    // freopen("tower.in","r",stdin);
    // freopen("tower.out","w",stdout);
    cin>>n>>q;
    vector<tuple<int,int,int>>Q;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=q;++i){
        int x,y;cin>>x>>y,Q.emplace_back(x,y,i);
    }
    solve(1,n,Q);
    for(int i=0;i<=q;++i)
        cout<<ans[i]<<'\n',ans[i+1]+=ans[i];
    return 0;
}
/*
*/