Eva

You come home and fell some unpleasant smell. Where is it coming from?

You are given an array a. You have to answer the following queries: 

1. You are given two integers l and r. Let ci be the number of occurrences of i in al: r, where al: r is the subarray of a from l-th element to r-th inclusive. Find the Mex of {c0, c1, ..., c109}

2. You are given two integers p to x. Change ap to x. 

The Mex of a multiset of numbers is the smallest non-negative integer not in the set.

Note that in this problem all elements of a are positive, which means that c0 = 0 and 0 is never the answer for the query of the second type.

The first line of input contains two integers n and q (1 ≤ n, q ≤ 100 000) — the length of the array and the number of queries respectively.

The second line of input contains n integers — a1, a2, ..., an (1 ≤ ai ≤ 109).

Each of the next q lines describes a single query.

The first type of query is described by three integers ti = 1, li, ri, where 1 ≤ li ≤ ri ≤ n — the bounds of the subarray.

The second type of query is described by three integers ti = 2, pi, xi, where 1 ≤ pi ≤ n is the index of the element, which must be changed and 1 ≤ xi ≤ 109 is the new value.

For each query of the first type output a single integer  — the Mex of {c0, c1, ..., c109}.

Input

Output

The subarray of the first query consists of the single element — 1. 

The subarray of the second query consists of four 2s, one 3 and two 1s.

The subarray of the fourth query consists of three 1s, three 2s and one 3.

#include<iosteam>

#include<cstdio>

#include<cmath>

#include<map>

using namespace std;

const int maxn=2e5+10;

int n,m,sz;

int a[maxn],nw[maxn];

int num[maxn],cnt[maxn],ans[maxn];

int be[maxn],siz;

map<int,int>mp;

struct node

{

    int l,r,ti,id;

    bool operator<(node aa)const

    {

        return be[l]==be[aa.l]?(be[r]==be[aa.r]?ti<aa.ti:r<aa.r):l<aa.l;

    }

}q[maxn];

int m1,m2;

struct Change

{

    int pos,nw,od;

}c[maxn];

 

int l,r,t;

void add(int i,int v)

{

    if(num[i]>0) cnt[num[i]]--;

    num[i]+=v;

    if(num[i]>0) cnt[num[i]]++;

}

void go(int i,int d)

{

    if(l<=i&&i<=r)

    {

        add(a[i],-1);

        add(d,1);

    }

    a[i]=d;

}

int getid(int x)

{

    if(!mp.count(x)) mp[x]=++siz;

    return mp[x];

}

 

int main()

{

    int T,cas=1;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        sz=pow(n,0.666666);

        memset(num,0,sizeof(num));

        memset(cnt,0,sizeof(cnt));

        mp.clear();

        siz=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&a[i]);

            nw[i]=a[i]=getid(a[i]);

            be[i]=(i-1)/sz+1;

        }

        m1=0;m2=0;

        for(int i=0;i<m;i++)

        {

            int op,x,y;

            scanf("%d%d%d",&op,&x,&y);

            if(op==1) q[++m1]=(node){x,y,m2,m1};

            else

            {

                y=getid(y);

                c[++m2]=(Change){x,y,nw[x]};

                nw[x]=y;

            }

        }

        sort(q+1,q+m1+1);

        l=1;r=0;t=0;

        for(int i=1;i<=m1;i++)

        {

            while(t<q[i].ti) {t++;go(c[t].pos,c[t].nw);}

            while(t>q[i].ti) {go(c[t].pos,c[t].od);t--;}

 

            while(l<q[i].l){add(a[l],-1);l++;}

            while(l>q[i].l){add(a[l-1],1);l--;}

            while(r<q[i].r){add(a[r+1],1);r++;}

            while(r>q[i].r){add(a[r],-1);r--;}

 

            int x=1;

            while(cnt[x]>0) x++;

            ans[q[i].id]=x;

        }

        for(int i=1;i<=m1;i++)

        {

            printf("%d\n",ans[i]);

        }

    }

    return 0;

}