#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("arbint.in");
ofstream g("arbint.out");
int N,M;
int v[100010];

struct elem {
    ll val=-1;
    elem* next=NULL;
};

struct arb_nod {
    elem* lista;
}arb[250010];

void creare(int,int,int,elem*&);
void adaugadescrescator(elem*,int);
void elimina(elem*,int);
void interclasare(elem*,elem*,elem*);
void actualizare(int,int,int,int,int);
ll interogare(int,int,int,int,int);
ll maxnr(elem*);

int main()
{
    f>>N>>M;
    FOR (i,1,N) {
        f>>v[i];
    }
    elem* p;
    creare(1,1,N,p);
    /*elimina(p,3);
    p=p->next;
    while (p->next!=NULL) {
        cout<<(p->val)<<' ';
        p=p->next;
    }*/
    FOR (i,1,M) {
        int tip,a,b;
        f>>tip>>a>>b;
        if (!tip) {
            g<<interogare(1,1,N,a,b)<<'\n';
        }
        else {
            actualizare(1,1,N,a,b);
            v[a]=b;
        }
    }
    /*p=arb[2].lista;
    p=p->next;
    while (p->next!=NULL) {
        cout<<(p->val)<<' ';
        p=p->next;
    }*/
    f.close();g.close();
    return 0;
}

void creare(int nod,int st,int dr,elem*& vect) {
    arb[nod].lista=new elem;
    adaugadescrescator(arb[nod].lista,-1);
    vect=arb[nod].lista;
    if (st==dr) {
        //cout<<st<<' '<<v[st]<<'\n';
        adaugadescrescator(arb[nod].lista,v[st]);
    }
    else {
        int mij=(st+dr)/2;
        elem *fiu_st,*fiu_dr;
        creare((nod<<1),st,mij,fiu_st);
        creare((nod<<1)+1,mij+1,dr,fiu_dr);
        fiu_st=fiu_st->next;
        fiu_dr=fiu_dr->next;
        interclasare(arb[nod].lista,fiu_st,fiu_dr);
    }
}

void adaugadescrescator(elem* lista,int x) {
    if (x!=-1) {
        lista=lista->next;
    }
    while ((lista->val)>x && lista->next!=NULL) {
        lista=lista->next;
    }
    elem* p=new elem;
    p->val=lista->val;
    p->next=lista->next;
    lista->val=x;
    lista->next=p;
}

void elimina(elem* lista,int val) {
    elem* p=lista;
    lista=lista->next;
    //cout<<"yes ";
    while (lista->val!=val) {
        p=lista;
        lista=lista->next;
    }
    //cout<<"yes\n";
    p->next=lista->next;
    delete lista;
}

void interclasare(elem* v,elem* st,elem* dr) {
    while (st->next!=NULL && dr->next!=NULL) {
        if (st->val<=dr->val) {
            adaugadescrescator(v,st->val);
            st=st->next;
        }
        else {
            adaugadescrescator(v,dr->val);
            dr=dr->next;
        }
    }
    while (st->next!=NULL) {
        adaugadescrescator(v,st->val);
        st=st->next;
    }
    while (dr->next!=NULL) {
        adaugadescrescator(v,dr->val);
        dr=dr->next;
    }
}

ll interogare(int nod,int st,int dr,int a,int b) {
    if (a<=st && dr<=b) {
        return maxnr(arb[nod].lista);
    }
    else {
        int mij=(st+dr)/2;
        ll max1=0;
        if (a<=mij) {
            max1=interogare((nod<<1),st,mij,a,b);
        }
        if (mij+1<=b) {
            max1=max(max1,interogare((nod<<1)+1,mij+1,dr,a,b));
        }
        return max1;
    }
}

ll maxnr(elem* lista) {
    lista=lista->next;
    return lista->val;
}

void actualizare(int nod,int st,int dr,int poz,int val) {
    if (st<=poz && poz<=dr) {
        //cout<<"yes ";
        elimina(arb[nod].lista,v[poz]);
        //cout<<"yes\n";
        adaugadescrescator(arb[nod].lista,val);
    }
    if (st<dr) {
        int mij=(st+dr)/2;
        if (poz<=mij) {
            actualizare((nod<<1),st,mij,poz,val);
        }
        if (mij+1<=poz) {
            actualizare((nod<<1)+1,mij+1,dr,poz,val);
        }
    }
}