#include <fstream>
using namespace std;
ifstream f("arbint.in");
ofstream g("arbint.out");
const int nmax=100005;
int arb[4*nmax+66],n,val,op,be/*gin*/,en/*d*/,poz,maxim,t,i;
void Updt (int nod ,int stanga , int dreapta)
{
int mijloc;
if (stanga==dreapta)
{
arb[nod]=val;
return;
}
else
mijloc=(stanga+dreapta)/2;
if (poz<=mijloc) Updt(2*nod,stanga,mijloc); // de ce 2*nod si 2*nod+1 ? pt ca orice nod n (care nu este terminal) are minim 2 fii , exact ca un heap , care sunt pe pozitiile 2*n si 2*n+1
else Updt(2*nod+1,mijloc+1,dreapta);
arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
void Quer (int nod, int stanga , int dreapta)
{
int mijloc;
if (be <= stanga && dreapta <= en) // daca ne incadram in interval
{
if (arb[nod]>maxim) maxim=arb[nod]; // de ce nu afisam direct maximul ? ei bine , nu tot timpul vom putea "prinde" perfect intervalul [a,b] ; ex: sa zicem ca avem intevalul de la 3 la 7 , si noi suntem la pasul in care avem nodul intervalului [3,5] , daca returnam chiar acum maximul , se omit punctele 6 si 7 , ceea ce nu este bine.
return;
}
mijloc=(stanga+dreapta)/2;
if (be<=mijloc) Quer(2*nod,stanga,mijloc); // practic , daca nu ne afalam in partea dorita a arborelui , tot mergem mai adanc , pana ce ajungem la capatul dorit , ex: daca suntem pe nodul intevralului [3,5] , si ne trebuie sa afisam maximul din intervalul [2,5] , mergem in stanga;
if (mijloc<en) Quer(2*nod+1,mijloc+1,dreapta);
}
int main()
{
f>>n>>t;
for (i=1;i<=n;i++)
{
f>>val;
poz=i;
Updt(1,1,n);
}
while (t--)
{
f>>op;
if (op==1)
{
f>>poz>>val;
Updt (1,1,n);
}
else
{
f>>be>>en;
maxim=-1;
Quer(1,1,n);
g<<maxim<<'\n';
}
}
f.close();
g.close();
return 0;
}