#include <fstream>
#include <cmath>
using namespace std;

ifstream f("arbint.in");
ofstream g("arbint.out");

int aux1,aux2,h=1,left_side,right_side,l,array1_lenght,number_of_questions,question,array1[100005],array2[420];
// array 1 is the initial one , array 2 is the descomposed one

void ReadFirstArray ()
{
    f>>array1_lenght>>number_of_questions;
    for (int i=1;i<=array1_lenght;i++)
     f>>array1[i];
}

int PositionInDescArray (int x)
{
   if (x<=l)
    return 1;
   if (x%l==0)
    return x/l;
   return x/l+1;
}

int BegginingOfSequence (int x)
{
    return l*(x-1)+1;
}

void CreateDescomposedArray()
{
    int i,j;
    l=sqrt(array1_lenght);

    for (i=1;i+l-1<=array1_lenght;i=i+l)
     {
        for (j=i;j<=i+l-1;j++)
             if (array1[j]>array2[h])
              array2[h]=array1[j];
        h++;
     }

     if (i<=array1_lenght)
      for (j=i;j<=array1_lenght;j++)
       if (array1[j]>array2[h])
        array2[h]=array1[j];
}

void UpdateDescArray()
{
    int position , new_value,sequence,j;
    f>>position>>new_value;
    array1[position]=new_value;
    sequence=PositionInDescArray(position);
    array2[sequence]=0;
    for (j=BegginingOfSequence(sequence);j<=BegginingOfSequence(sequence)+l-1;j++)
      if (array1[j]>array2[sequence])
        array2[sequence]=array1[j];
}

void Answer()
{
    int aux1,aux2,maximum,j;
     f>>left_side>>right_side;
           aux1=PositionInDescArray(left_side);
           aux2=PositionInDescArray(right_side);

           if (aux1==aux2 || aux1==aux2-1)
            {
                maximum=0;
                for (j=left_side;j<=right_side;j++)
                 if (array1[j]>maximum)
                  maximum=array1[j];
                g<<maximum<<'\n';
            }

           else
           {
               maximum=0;
               for (j=aux1+1;j<=aux2-1;j++)
                if (array2[j]>maximum)
                 maximum=array2[j];

               for (j=left_side;j<=BegginingOfSequence(aux1)+l-1;j++)
                if (array1[j]>maximum)
                 maximum=array1[j];

               for (j=BegginingOfSequence(aux2);j<=right_side;j++)
                if (array1[j]>maximum)
                 maximum=array1[j];

               g<<maximum<<'\n';
           }
}

void AnswerQuestions ()
{
      for (int i=1;i<=number_of_questions;i++)
       {
           f>>question;
           if (question)
            UpdateDescArray();
           else Answer();
       }
}

int main()
{
    ReadFirstArray();
    CreateDescomposedArray();
    AnswerQuestions();
    f.close();
    g.close();
    return 0;
}