#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int main()
{
    ifstream f("arbint.in");
    ofstream g("arbint.out");
    int n,m,x,y,a[15001],b[400],i,j,maxi,huh,nr,poz,poz1,s,cod;
    f>>n>>m;
    nr=n/(int)sqrt(n);
    if(nr*(int)sqrt(n)!=n)
      nr++;
    j=1;
    huh=0;
    maxi=-1;
    for(i=1;i<=n;++i)
      {f>>a[i];
          if(j<=(int)sqrt(n))
            {if(a[i]>maxi)
                  maxi=a[i];
                j++;}
            else
            {   j=2;
                huh++;
                b[huh]=maxi;
                maxi=a[i];}
      }
    huh++;
    b[huh]=maxi;
    s=(int)sqrt(n);
    for(int ii=1;ii<=m;++ii)
      {
          f>>cod>>x>>y;
          if(x%s==0)
                poz=x/s;
                else
                poz=x/s+1;
          if(y%s==0)
                poz1=y/s;
                else
                poz1=y/s+1;
          //g<<x<<"  "<<y<<"  "<<poz<<"  "<<poz1<<"  - cod=  "<<cod<<endl;
          if(cod==0)
            {
                if(x==y)
                  g<<a[x]<<'\n';
                  else
                if(poz==poz1)
                  {   maxi=-1;
                      for(i=x;i<=y;i++)
                        if(maxi<a[i])
                          maxi=a[i];
                      g<<maxi<<'\n';}
                else
                {maxi=-1;
                if(poz1-poz>1)
                     for(i=poz+1;i<=poz1-1;i++)
                        if(b[i]>maxi)
                          maxi=b[i];
                i=x;
                while(i<=poz*s)
                  {if(a[i]>maxi)
                         maxi=a[i];
                      i++;}
                  i=y;
                  while(i>(poz1-1)*s)
                    {if(a[i]>maxi)
                      maxi=a[i];
                      i--;}
                g<<maxi<<'\n';}
            }
            else
                {if(y>b[poz])
                   {b[poz]=y;  a[x]=y;}
                   else
                 if(a[x]==b[poz])
                    {
                        a[x]=y;
                        b[poz]=y;
                        for(int h=(poz-1)*s+1;h<=poz*s;++h)
                           if(a[h]>b[poz])
                             b[poz]=a[h]; }
                    else
                    a[x]=y;
                }
      }
    f.close();
    g.close();
    return 0;
}