#include <fstream>
#include <math.h>
using namespace std;

int a[100100];
int batog[400];
ifstream in("arbint.in");
ofstream out("arbint.out");
int impartire,n,nr_impartiri,nrop;

int maximum(int a,int b)
{
    if(a>=b)return a;
    return b;
}

int minim(int a, int b)
{
    if(a<=b)return a;
    return b;
}

void max_int(int arg1,int arg2)
{
    int maxim = a[arg1];
    while(arg1%impartire!=1&&arg1<=arg2)
    {
        maxim=maximum(maxim,a[arg1]);
arg1++;

    }
    while (arg2 % impartire != 1 && arg1 <= arg2)
    {
        maxim=maximum(maxim,a[arg2]);
arg2--;


    }
    while (arg1 <= arg2)
    {
        maxim = maximum(maxim, batog[(arg1 - 1) / impartire + 1]);
        arg1 += impartire;


    }
    out << maxim << "\n";

}

void calculare_batog(int y)
{
    int lim_inf = (y - 1) * impartire + 1;
    int lim_sup = minim(y * impartire, n);
    batog[y] = a[lim_inf];
    for (int i = lim_inf + 1; i <= lim_sup; ++ i)
    {


        batog[y] = maximum(batog[y], a[i]);


    }


}

void schimb(int arg1,int arg2)
{


    a[arg1] = arg2;
    int y = (arg1 - 1) / impartire + 1;
    calculare_batog(y);



}

void generare_batog()
{
    for (int y = 1; y <= nr_impartiri; ++ y)
    {
        calculare_batog(y);
    }

}

int main()
{

    in >> n >> nrop;
    int op, arg1, arg2;
    impartire = maximum(1, minim(n, (int)sqrt((float)n)));
    nr_impartiri = n / impartire;
    for (int i = 1; i <= n; ++ i)
    {
        in >> a[i];
    }

    for (int i = 1; i <= nrop; ++ i)
    {
        in >> op >> arg1 >> arg2;


        if (op == 1)
        {

            schimb(arg1,arg2);


        }
        else
        {
            max_int(arg1,arg2);


        }


    }

    return 0;
}