#include<fstream>
#include<cstdlib>
#include<ctime>
#define FOR(a,b,c) for(int a=b;a<=c;++a);
using namespace std;
ifstream f("arbint.in");
ofstream g("arbint.out");
int a,b,sol,n,x,tip,m;
struct Tr
{
    Tr *l,*r;
    int cnt,pr,val,ma;
    Tr() {};
    Tr(int _cnt,int _pr,int _val)
    {
        l=r=NULL;
        cnt=_cnt;
        ma=val=_val;
        pr=_pr;
    }
};
#define T Tr*
T R;
int cnt(T t)
{
    if(!t)
    return 0;
    return t->cnt;
}
int ma(T t)
{
    if(!t)
    return 0;
    return t->ma;
}
void upd(T &t)
{
    if(!t)
    return ;
    t->cnt=cnt(t->l)+cnt(t->r)+1;
    t->ma=max(t->val,max(ma(t->l),ma(t->r)));
}
void split(T t,T &l,T &r,int k,int add)
{
    if(!t)
        return void(l=r=NULL);
    int cur_key=add+cnt(t->l)+1;
    if(k<=cur_key)
    split(t->l,l,t->l,k,add),r=t;
    else
    split(t->r,t->r,r,k,cur_key),l=t;
    upd(t);
}
void merge(T &t,T l,T r)
{
    if(!l||!r)
        t=l?l:r;
    else
    if(l->pr > r->pr)
    merge(l->r,l->r,r),t=l;
    else
    merge(r->l,l,r->l),t=r;
    upd(t);
}
void insert(T &t,T it,int add)
{
    if(!t)
    {
        t=it;
        return;
    }
    int cur_key=add+cnt(t->l)+1;
    if(it->pr > t->pr)
        split(t,it->l,it->r,it->cnt,add),t=it;
    else
    if(it->cnt > cur_key)
        insert(t->r,it,cur_key);
    else
        insert(t->l,it,add);
    upd(t);
}
void erase(T &t,int k,int add)
{
    int cur_key=add+cnt(t->l)+1;
    if(cur_key==k)
    merge(t,t->l,t->r);
    else
    if(k>cur_key)
        erase(t->r,k,cur_key);
    else
        erase(t->l,k,add);
    upd(t);
}
void query(T &t,int st,int dr,int add)
{
    if(!t)
    return ;
    if(add+1>=st&&add+cnt(t)<=dr)
    {
        sol=max(sol,t->ma);
    }
    int cur_key=add+cnt(t->l)+1;
    if(cur_key>=st&&cur_key<=dr)
    sol=max(sol,t->val);
    if(cur_key-1>=st)
    query(t->l,st,dr,add);
    if(cur_key+1<=dr)
    query(t->r,st,dr,cur_key);
}
int main ()
{
    srand(time(0));
    f>>n>>m;
    FOR(i,1,n)
    {
        f>>x;
        T it=new Tr(a,rand()+1,x);
        insert(R,it,0);
    }
    FOR(i,1,m)
    {
        f>>tip;
        if(!tip)
        {
            f>>a>>b;
            sol=0;
            query(R,a,b,0);
            g<<sol<<"\n";
        }
        else
        {
            f>>a>>b;
            erase(R,a,0);
            T it=new Tr(a,rand()+1,b);
            insert(R,it,0);
        }
    }
    return 0;
}