#include <fstream>
#include <bits/stdc++.h>
#define mp make_pair
#define VAL 12345678901

using namespace std;

int x;

struct T
{
    int key,pr,maxx,val;
    T *left,*right;
    T(int X, int XX)
    {
        key=X; pr=rand()%VAL; left=right=0;
        val=XX;
    }
} *root = 0;

inline int Maxx(T *nod)
{
    if(nod==0) return 0;
    return nod->maxx;
}

inline void Upd(T *nod)
{
    if(nod==0) return;
    nod->maxx=max(nod->val,max(Maxx(nod->left),Maxx(nod->right)));
}

inline pair <T*,T*> Split(T *nod, int k)
{
    if(nod==0) return mp((T*) 0, (T*) 0);
    pair <T*,T*> spl;
    if(k<=nod->key)
    {
        spl=Split(nod->left,k);
        nod->left=spl.second; spl.second=nod;
        Upd(nod);
    }
    else
    {
        spl=Split(nod->right,k);
        nod->right=spl.first; spl.first=nod;
        Upd(nod);
    }
    return spl;
}

inline T *Merge(T *L, T *R)
{
    Upd(L); Upd(R);
    if(L==0) return R;
    if(R==0) return L;
    if(L->pr <= R->pr)
    {
        R->left=Merge(L,R->left);
        Upd(R);
        return R;
    }
    L->right=Merge(L->right,R);
    Upd(L);
    return L;
}

inline T *Erase(T *nod, int k)
{
    if(k<nod->key) nod->left=Erase(nod->left,k);
    else
        if(k>nod->key) nod->right=Erase(nod->right,k);
        else
        {
            T *aux=Merge(nod->left,nod->right);
            delete(nod);
            nod=aux;
        }
    Upd(nod);
    return nod;
}

inline int Query(int st, int dr)
{
    pair <T*,T*> spl=Split(root,st);
    pair <T*,T*> spl1=Split(spl.second,dr+1);
    int sol = spl1.first -> maxx;
    root=Merge(spl.first,Merge(spl1.first,spl1.second));
    return sol;
}

inline T *Insert(int k, int val)
{
    pair <T*,T*> spl=Split(root,k);
    return Merge(Merge(spl.first,new T(k,val)),spl.second);
}

int main()
{
    int i,m,n,tip,p;
    ifstream cin("arbint.in");
    ofstream cout("arbint.out");
    srand(time(0));
    cin>>n>>m;
    for(i=1;i<=n;++i)
    {
        cin>>x; root=Insert(i,x);
    }
    while(m--)
    {
        cin>>tip>>p>>x;
        if(!tip) cout<<Query(p,x)<<"\n";
        else
        {
            Erase(root,p);
            Insert(p,x);
        }
    }
    return 0;
}