#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],b[N+M],ans[M];
set<int>pre[N+M],suf[N+M];
int Fa[N+M],Fb[N+M],Ta[(N+M)*4],Tb[(N+M)*4],S[(N+M)*4];
inline int qry(int p,int l,int r,int a,int b){
    if(Fa[r]<=a&&Fb[r]<=b)return S[p];
    if(a<Ta[p]||b<Tb[p])return 0;
    const int mid=(l+r)>>1;
    if(Ta[p*2+1]<=a&&Tb[p*2+1]<=b)return qry(p*2+1,mid+1,r,a,b)+S[p]-S[p*2+1];
    else return qry(p*2,l,mid,min(a,Ta[p*2+1]),min(b,Tb[p*2+1]));
}
inline void build(int p,int l,int r){
    if(l==r){
        Ta[p]=(Fa[l]=pre[l].empty()?INF:*pre[l].begin());
        Tb[p]=(Fb[l]=suf[l].empty()?INF:*suf[l].begin());
        S[p]=1;
        return;
    }
    const int mid=(l+r)>>1;
    build(p*2,l,mid),build(p*2+1,mid+1,r);
    Ta[p]=min(Ta[p*2],Ta[p*2+1]),Tb[p]=min(Tb[p*2],Tb[p*2+1]);
    S[p]=S[p*2+1]+qry(p*2,l,mid,Ta[p*2+1],Tb[p*2+1]);
}
inline void upd(int p,int l,int r,int x){
    if(l==r){
        Ta[p]=(Fa[l]=pre[l].empty()?INF:*pre[l].begin());
        Tb[p]=(Fb[l]=suf[l].empty()?INF:*suf[l].begin());
        S[p]=1;
        return;
    }
    const int mid=(l+r)>>1;
    x<=mid?upd(p*2,l,mid,x):upd(p*2+1,mid+1,r,x);
    Ta[p]=min(Ta[p*2],Ta[p*2+1]),Tb[p]=min(Tb[p*2],Tb[p*2+1]);
    S[p]=S[p*2+1]+qry(p*2,l,mid,Ta[p*2+1],Tb[p*2+1]);
}
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;
    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;
    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);
    build(1,1,m);
    int lans=qry(1,1,m,-l,r);
    ans[0]+=lans;
    for(auto [x,y,id]:nQ){
        y=lower_bound(b+1,b+m+1,y)-b;
        int z=A[x];
        if(y!=z){
            ans[id]-=lans;
            if(x<=mid)pre[z].erase(-x),pre[y].emplace(-x);
            else suf[z].erase(x),suf[y].emplace(x);
            A[x]=y,upd(1,1,m,z),upd(1,1,m,y);
            ans[id]+=(lans=qry(1,1,m,-l,r));
        }
    }
    for(int i=1;i<=m;++i)pre[i].clear(),suf[i].clear();
    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;
}
/*
*/