#include <fstream>
using namespace std;

ifstream cin("arbint.in");
ofstream cout("arbint.out");

struct treap{
    int poz,val,prioritate;
    treap *st,*dr;
    int minpoz,maxpoz,maxval;
    treap(treap *l,treap *r,int pozz,int vall,int prioritatee,int min1,int max1){
        st=l;dr=r;
        poz=pozz;
        maxval=val=vall;
        prioritate=prioritatee;
        minpoz=min1;maxpoz=max1;
    }
};

treap *NILL=new treap(nullptr,nullptr,-1,-1e9,-1,1e9,-1e9);

void rotatie_st(treap *& nod){
    treap *aux=nod->dr;
    nod->dr=aux->st;
    aux->st=nod;
    nod=aux;
}

void rotatie_dr(treap *& nod){
    treap *aux=nod->st;
    nod->st=aux->dr;
    aux->dr=nod;
    nod=aux;
}

void recheck(treap *& nod){
    if(nod==NILL) return ;
    nod->maxval=nod->val;
    nod->maxval=max(nod->maxval,nod->st->maxval);
    nod->maxval=max(nod->maxval,nod->dr->maxval);
    nod->minpoz=min(nod->poz,nod->st->minpoz);
    nod->maxpoz=max(nod->poz,nod->dr->maxpoz);
}

void balance(treap *& nod){
    if(nod==NILL) return;
    if(nod->prioritate<nod->st->prioritate) rotatie_dr(nod);
    if(nod->prioritate<nod->dr->prioritate) rotatie_st(nod);
    recheck(nod->st);
    recheck(nod->dr);
    recheck(nod);
}

int generate_random_nr(){
    return abs((1ll*rand()<<15)+rand())%1000000000+1;
}

void insertie(treap *& nod,int poz,int val){
    if(nod==NILL){
        nod=new treap(NILL,NILL,poz,val,generate_random_nr(),poz,poz);
        return ;
    }
    if(poz<nod->poz){
        insertie(nod->st,poz,val);
    }else{
        insertie(nod->dr,poz,val);
    }
    balance(nod);
}

int find_max(treap *& nod,int st,int dr){

    if(nod==NILL) return -1e9;
    int maxst=-1e9,maxdr=-1e9,maxcur=-1e9;
    ///printf("%d %d %d\n",maxst,maxdr,nod->minpoz);

    if(st<=nod->minpoz && nod->maxpoz<=dr) return  nod->maxval;
    if(st<=nod->poz && nod->poz<=dr) maxcur=nod->val;
    if(st<=nod->st->maxpoz){
        maxst=find_max(nod->st,st,dr);
    }
    if(nod->dr->minpoz<=dr){
        maxdr=find_max(nod->dr,st,dr);
    }
    return max(maxcur,max(maxst,maxdr));
}

void sterge(treap *& nod,int poz){
    if(nod==NILL) return;
    if(poz<nod->poz){
        sterge(nod->st,poz);
    }else if(poz>nod->poz){
        sterge(nod->dr,poz);
    }else{
        if(nod->st==NILL && nod->dr==NILL){
            delete nod;
            nod=NILL;
        }else if(nod->st->poz<nod->dr->poz){
            rotatie_st(nod);
            sterge(nod,poz);
        }else{
            rotatie_dr(nod);
            sterge(nod,poz);
        }
    }
    balance(nod);
}

int main()
{
    int n,m,i,cer,a,b;
    cin>>n>>m;
    srand(6565);
    treap *root=NILL;
    for(i=1;i<=n;i++){
        cin>>a;
        insertie(root,i,a);
    }
    for(i=1;i<=m;i++){

        cin>>cer>>a>>b;
        if(cer==0) cout<<find_max(root,a,b)<<"\n";
        else{
            sterge(root,a);
            insertie(root,a,b);
        }
         ///printf("\n");
    }
    return 0;
}