/*arbori intervale
problema arbint de pe infoarena
arborele de intervale va retine o prelucrare a unui anumit interval
radacina are asociata intervalul 1,N, fiul stang intervalul 1, (1+N)/2, fiul drept (1+N)/2+1, N
frunzele vor retine intervale de un element, practic elementele vectorului
codificam arborele de intervale ca fiind un vector cu definitia
arb[1]=valoarea asociata intervalului 1,N
arb[2]=valoarea asociata intervalului 1,(N+1)/2
arb[3]=valoarea asociata intervalului N+1)/2+1,N
In general, fiul stang al componentei nod va fi 2*nod, iar fiul drept 2*nod+1
Un arbore de intervale are 2 operatii elementare, actualizarea unei pozitii pos cu o valoare val si interogarea unui interval (a,b)
Prin update se construieste in mod repetat arborele, pornind de la frunze. La fiecare nod adaugat se actualizeaza si informatiile
din nodurile anterioare
Se foloseste divide et impera
Vectorul arb retine arborele de intervale, Deoarece este un arbore binar, nr de noduri este cea mai mica putere a lui 2 mai mare
decat 2*N+1.Daca N este 100000, cea mai apropiata putere este 262144, luam ptr siguranta 263000

Nu avem nevoie de un vector pentru memorarea elementelor

Pentru a gasi maximul unui interval procedam tot dupa tehnica divide et impera si ne folosim de vectorul de intervale
Cazul trivial: intervalul dat contine un interval din arbore. intoarcem valoarea din acel nod asociat
altfel verificam daca capatul din stanga este mai mic sau egal cu mijlocul intervalului, in acest caz continuam reapelarea
cu fiul stang, deoarece vom interoga in intervalul st,mij. Verificam si daca capatul din dreapta este mai mare decat mij si reapelam
cu fiul drept cresp intervalului div+1,dr
Apoi combinam cele doua rezultate, intorcand maximul
*/

#include<fstream>
#define dim 263000
using namespace std;

ifstream fin("arbint.in");
ofstream fout("arbint.out");

int arb[dim],N,M;

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

//functia de actualizare, o vom folosi ptr constructia arborelui de intervale si apoi ptr al doilea punct al problemei
void update(int nod, int pos, int val,int st, int dr)
{
    //daca avem capete egale suntem in cazul intervalului elementar dorit, actualizam pos cu val
    if(st==dr)
    {
        arb[nod]=val;
    }
    else
    {
        //calculam mijlocul
        int mij=(st+dr)/2;
        //daca pozitia este mai mica sau egala decat mijlocul, apelam cu intervalul st,mij si nodul 2*nod,
        //altfel cu intervalul mij+1,dr si nodul 2*nod+1
        if(pos<=mij)
            update(2*nod,pos,val,st,mij);
        else
            update(2*nod+1,pos,val,mij+1,dr);
        //actualizam valoarea de pe pozitia nod (combin rezultatele de pe cele doua intervale)
        arb[nod]=maxim(arb[2*nod], arb[2*nod+1]);
    }
}

//functia de interogare a unui interval dat ca parametru
int query(int nod, int st, int dr, int a, int b)
{
    int rez1=0,rez2=0;
    if(a<=st && dr<=b)
        return arb[nod];
    else
    {
        int mij=(st+dr)/2;
        if(a<=mij)
            rez1=query(2*nod,st,mij,a,b);
        if(mij<b)
            rez2=query(2*nod+1,mij+1,dr,a,b);
        return maxim(rez1,rez2);
    }
}

int main()
{
    int x,i,c,a,b;
    fin>>N>>M;
    for(i=1;i<=N;i++)
    {
        fin>>x;
        update(1,i,x,1,N);
    }
    for(i=1;i<=M;i++)
    {
        fin>>c>>a>>b;
        if(c==0)
            fout<<query(1,1,N,a,b)<<"\n";
        else
            update(1,a,b,1,N);
    }
    return 0;
}