/*
de ce fac o sursa de batog cu heapuri ca sa ia 100 cand trebuie sa ia numa 50 victore culca-te
*/
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define QUERY 0
#define UPDATE 1
#define INF 1000000000
#define N 100000
#define SQN 512
const int BSIZE = (N - 1) / SQN + 1;

using std::max;
using std::swap;

int v[N];
int batog[BSIZE];
int heap[BSIZE][SQN];
int nheap[BSIZE];
int pozInHeap[N];
int n;

inline int getBucket( int poz ) { return poz / SQN; }
inline int firstPosBucket( int bucket ) { return bucket * SQN; }
inline int lastPosBucket( int bucket ) { return firstPosBucket( bucket ) + SQN - 1; }

// functii pentru heap
inline int parent( int node ) { return (node - 1) / 2; }
inline int leftChild( int node ) { return node * 2 + 1; }
inline int rightChild( int node ) {  return node * 2 + 2; }

void upHeap( int bucket, int node ) {
    while ( node > 0 && v[heap[bucket][node]] > v[heap[bucket][parent( node )]] ) {
        swap( heap[bucket][node], heap[bucket][parent( node )] );
        swap( pozInHeap[heap[bucket][node]], pozInHeap[heap[bucket][parent( node )]] );
        node = parent( node );
    }
}

void downHeap( int bucket, int node ) {
    int left, right, maxx;

    left = leftChild( node );
    right = rightChild( node );
    maxx = node;

    if ( left < nheap[bucket] && v[heap[bucket][left]] > v[heap[bucket][maxx]] )
        maxx = left;
    if ( right < nheap[bucket] && v[heap[bucket][right]] > v[heap[bucket][maxx]] )
        maxx = right;
    if ( node != maxx ) {
        swap( heap[bucket][node], heap[bucket][maxx] );
        swap( pozInHeap[heap[bucket][node]], pozInHeap[heap[bucket][maxx]] );
        downHeap( bucket, maxx );
    }
}

inline void addToHeap( int bucket, int poz ) {
    heap[bucket][nheap[bucket] ++] = poz;
    pozInHeap[poz] = nheap[bucket] - 1;
    upHeap( bucket, nheap[bucket] - 1 );
}

inline void removeMin( int bucket ) {
    int aux = heap[bucket][0];
    heap[bucket][0] = heap[bucket][-- nheap[bucket]];
    downHeap( bucket, 0 );
    //pozInHeap[aux] = 0;
}

inline void removeFromHeap( int bucket, int node ) {
    heap[bucket][node] = heap[bucket][0];
    upHeap( bucket, node );
    removeMin( bucket );
}

void build() {
    for ( int i = 0; i < BSIZE; i ++ )
        batog[i] = 0;
    for ( int i = 0; i < n; i ++ ) {
        batog[i / SQN] = max( batog[i / SQN], v[i] );
        addToHeap( i / SQN, i );
    }
}

void update( int poz, int val ) {
    int bucket = getBucket( poz );
    removeFromHeap( bucket, pozInHeap[poz] );
    v[poz] = val;
    addToHeap( bucket, poz );
    batog[bucket] = heap[bucket][0];
}

int query( int st, int dr ) {
    int ans = -INF, lb, rb;

    lb = lastPosBucket( getBucket( st ) );
    rb = firstPosBucket( getBucket( dr ) );

    if ( lb > rb ) { // nu am niciun bucket in interval
        while ( st <= dr )
            ans = max( ans, v[st ++] );
        return ans;
    }

    while ( st <= lb )
        ans = max( ans, v[st ++] );
    for ( ; st < rb; st += SQN )
        ans = max( ans, batog[getBucket( st )] );
    while ( st <= dr )
        ans = max( ans, v[st ++] );
    return ans;
}

int main() {
    FILE *fin, *fout;
    int q, pb, a, b;

    fin = fopen( "arbint.in", "r" );
    fout = fopen( "arbint.out", "w" );
    fscanf( fin, "%d%d", &n, &q );
    for ( int i = 0; i < n; i ++ )
        fscanf( fin, "%d", &v[i] );
    build();
    for ( int i = 0; i < q; i ++ ) {
        fscanf( fin, "%d%d%d", &pb, &a, &b );
        if ( pb == QUERY )
            fprintf( fout, "%d\n", query( a - 1, b - 1 ) );
        else if ( pb == UPDATE )
            update( a - 1, b );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}