/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 31, 2010, 9:40 AM
 */
#include <fstream>
#define NMax 100001
#define inf 0x3f3f3f3f

/*
 *
 */
using namespace std;
int N;
int v[NMax], tree[NMax];
inline int max( int x, int y )
{
    return ( v[x] > v[y] ? x : y );
}
int Query( int x, int y )
{int maxim=0, idx1, idx2;
    for( idx1=y-( y & -y ); x <= y; y=idx1, idx1-=( idx1 & -idx1 )  )
    {
        if( idx1 >= x )
            idx2=tree[y];
        else idx1=y-1, idx2=idx1+1;
        maxim=max( idx2, maxim );
    }
    return maxim;
}
int Update( int x )
{
    for( int z=x; z <= N; z+=( z & -z ) )
        if( x == tree[z] )
          tree[z]=max( z, Query( z-( z & -z )+1 , z-1 ) );
        else tree[z]=max( tree[z], x );
}
int main()
{int m, i, x, y, z;
    ifstream in("arbint.in");
    in>>N>>m;
    v[0]=-inf;
    for( i=1; i <= N; ++i )
    {
        in>>v[i];
        Update( i );
    }
    ofstream out("arbint.out");
    for( i=1; i <= m; ++i )
    {
        in>>x>>y>>z;
        if( 0 == x )
            out<<v[ Query( y, z ) ]<<'\n';
        else v[y]=z, Update( y );
    }
    return 0;
}