#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 1000100
#define oo (1<<30)
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

int n,q,a[N],pre[N];
bool vis[N];

struct BIT
{
    int c[N];
    IL int low(reg int x){return x&-x;}
    IL int ask(reg int x){reg int r=0; for(;x;x-=low(x))r+=c[x]; return r;}
    IL void add(reg int x,reg int k){for(;x<=n;x+=low(x))c[x]+=k;}
}A;

int pos[N];
std::set<int>s[N];

struct Segment
{
    #define ls (o<<1)
    #define rs (o<<1|1)
    #define mid (l[o]+r[o]>>1)

    int l[N<<2],r[N<<2],tag[N<<2];
    struct info{int x,y;}tr[N<<2];

    IL int min(reg int x,reg int y){return x<y?x:y;}

    IL info merge(const info &a,const info &b)
    {
        info c={min(a.x,b.x),a.y};
        if(a.x!=c.x)c.y=b.y;
        return c;
    }

    IL void pushup(reg int o){tr[o]=merge(tr[ls],tr[rs]);}
    IL void apply(reg int o,reg int k){tr[o].x+=k,tag[o]+=k;}
    IL void pushdown(reg int o){if(tag[o])apply(ls,tag[o]),apply(rs,tag[o]),tag[o]=0;}

    void build(reg int o,reg int L,reg int R)
    {
        l[o]=L,r[o]=R,tr[o]={oo,L};
        if(L<R)build(ls,L,mid),build(rs,mid+1,R);
    }

    void modify(reg int o,reg int L,reg int R,reg int k)
    {
        if(L<=l[o]&&r[o]<=R)return apply(o,k);
        if(L>r[o]||l[o]>R)return;
        pushdown(o),modify(ls,L,R,k),modify(rs,L,R,k),pushup(o);
    }

    void insert(reg int o,reg int p,reg int k)
    {
        if(l[o]==r[o])tr[o]={k,p};
        else pushdown(o),insert(mid>=p?ls:rs,p,k),pushup(o);
    }

    #undef ls
    #undef rs
    #undef mid
}f,g;

namespace SET
{

IL void ins(reg int x) // insert to S
{
    vis[x]=1,A.add(x,1);
}

IL void del(reg int x) // delete from S
{
    vis[x]=0,A.add(x,-1);
}

IL int kth(reg int k) // kth among elements not in S
{
    if(!k)return 0;
    reg int i=0;
    for(reg int o=20;o--;)if(i+(1<<o)<=n&&(1<<o)-A.c[i+(1<<o)]<k)
        k-=(1<<o)-A.c[i+=(1<<o)];
    return i+1;
}

}

IL void del(reg int x)
{
    if(!x)return;
    if(!vis[a[x]])return g.insert(1,a[x],oo);
    SET::del(a[x]);
    f.insert(1,a[x],oo);
    f.modify(1,a[x]+1,n,1);
    g.modify(1,a[x]+1,n,-1);
    auto [u,v]=g.tr[1];
    if(u==-1)
    {
        f.modify(1,v+1,n,-1);
        g.modify(1,v+1,n,1);
        SET::ins(v);
        f.insert(1,v,1),g.insert(1,v,oo);
    }
}

IL void ins(reg int x)
{
    if(!x)return;
    reg int k=a[x]-pre[x]-A.ask(a[x]-1);
    if(k<=0)return g.insert(1,a[x],-k);
    SET::ins(a[x]);
    f.insert(1,a[x],k);
    f.modify(1,a[x]+1,n,-1);
    g.modify(1,a[x]+1,n,1);
    auto [u,v]=f.tr[1];
    if(!u)
    {
        f.modify(1,v+1,n,1);
        g.modify(1,v+1,n,-1);
        SET::del(v);        
        f.insert(1,v,oo),g.insert(1,v,0);
    }
}

main()
{
    n=read(),q=read();
    for(reg int i=1;i<=n;++i)a[i]=read();
    for(reg int i=1;i<=n;++i)pre[i]=pre[i-1]+(a[i]==0);
    f.build(1,1,n),g.build(1,1,n);
    for(reg int x,k,y;q--;)
    {
        x=read(),k=read(),y=read();
        if(~a[x])
        {
            del(pos[a[x]]),s[a[x]].erase(x);
            if(s[a[x]].empty())pos[a[x]]=0;
            else pos[a[x]]=*s[a[x]].begin();
            ins(pos[a[x]]);
        }
        a[x]=k;
        if(~k)
        {
            del(pos[k]),s[k].insert(x);
            pos[k]=*s[k].begin(),ins(pos[k]);
        }
        if(a[y])printf("%d\n",a[y]);
        else printf("%d\n",SET::kth(pre[y]));
    }
}