#include <bits/stdc++.h>
using namespace std;
ifstream fin ("arbint.in");
ofstream fout("arbint.out");
int const lmax=100007;
int n,m,v[lmax];
int aib1[lmax];
int aib2[lmax];
void UPDATE(int pos, int val)
{
    int oldValue=v[pos];
    v[pos]=val;
    int copyval=val;
    int node=pos;
    ///aib1
    while (node<=n)
    {
        if (val<aib1[node])
        {
            if(oldValue==aib1[node])
            {
                val=max(val,v[node]);
                int aux=__builtin_ctz(node);
                for(int i=0;i<aux;i++)
                {
                    int child=node-(1<<i);
                    val=max(val,aib1[child]);
                }
            }
            else break;
        }
        if (val==aib1[node]) break;
        aib1[node]=val;
        node+=(node&-node);
    }
    ///aib2
    node=pos;
    val=copyval;
    while (node>0)
    {
        if (val<aib2[node])
        {
            if(oldValue==aib2[node])
            {
                val=max(val,v[node]);
                int aux=__builtin_ctz(node);
                for(int i=0;i<aux;i++)
                {
                    int child=node+(1<<i);
                    val=max(val,aib2[child]);
                }
            }
            else break;
        }
        if (val==aib2[node]) break;
        aib2[node]=val;
        node-=(node&-node);
    }

}
int QUERY(int st, int dr)
{
    int val=-1;
    for(int i=dr;i-(i&-i)>=st;i-=(i&-i))
    {
        val=max(val,aib1[i]);
    }
    int i=st;
    for(;i+(i&-i)<=dr;i+=(i&-i))
    {
        val=max(val,aib2[i]);
    }
    val=max(val,v[i]);
    return val;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int h;
        fin>>h;
        UPDATE(i,h);
    }
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        fin>>c>>a>>b;
        if(c==1)
        {
            UPDATE(a,b);
        }
        else fout<<QUERY(a,b)<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}