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

#define in "arbint.in"
#define out "arbint.out"
#define maxim(a,b) ((a)>(b)?(a):(b))
#define mod(x) ((x)<(0)?(-x):(x))

const int NMAX = 100005;
const int MAXMAX = 317;
int M, N;
int A[NMAX];
int mx[MAXMAX];

void Build( int K )
{
     int i, cnt;
     mx[cnt=0] = *A;
     for ( i = 1; i < N; ++i )
     {
         if ( i % K == 0 ) cnt++;
         mx[cnt] = maxim(mx[cnt],*(A+i));
     }
}   

void Update ( int a, int b, int K )
{
     *(A+a) = b;
     int t, C1 = a/K, sol_max = *(A+C1*K);;
     for ( t = C1*K+1; t != ((C1+1)*K); ++t )
         sol_max = maxim(sol_max,*(A+t) );
     mx[C1] = sol_max;
}         

int ReturnMax( int i, int j, int K )
{
    bool x, y;
    int t,C1,C2, sol_max = 0;
    x = y = false;
    
    C1 = i/K;
    C2 = j/K;
    
    if ( mod(C2-C1) <= 1 )
    {
         for ( t = i; t <= j; ++t )
             sol_max = maxim(sol_max,*(A+t) );
    }
    else
    {
        if ( i%K == 0 ) x = true;
        if ( !x )
        {
             for ( t = i; t; ++t ) {
                 if ( t%K == 0 ) break; 
                 sol_max = maxim(sol_max,*(A+t)); 
             }
        }
        if ( j%K == K-1 ) y = true;
        if ( !y )
        {
             for ( t = j; t; --t ) {
                 if ( t%K == K-1 ) break;
                 sol_max = maxim(sol_max,*(A+t) );
             }
        }
        for ( t = C1+1; t < C2; ++t ) sol_max = maxim ( sol_max, mx[t] );
        if ( x ) sol_max = maxim (sol_max, mx[C1] );
        if ( y ) sol_max = maxim ( sol_max, mx[C2] );
    }
    return sol_max;
}

int main( void )
{
    freopen ( in, "r", stdin );
    freopen ( out, "w", stdout );
    
    scanf ( "%d%d", &N, &M );
    
    int i, op, a, b, K=0;
    
    while ( K*K <= N ) K++;
    K--;
    if ( K*K != N ) K += 1;
    
    for ( i = 0; i < N; scanf ( "%d", (A+i++) ));
    Build( K );
    
    for ( ; M; --M )
    {
        scanf ("%d%d%d", &op,&a,&b );
        if ( op ) Update ( a-1, b, K);
        else printf ( "%d\n", ReturnMax(a-1,b-1,K) );
    }
    
    return 0;
}