#include <fstream>
#include <iostream>
using namespace std;
int generate_rand(){
	return abs( ( ( 1ll * rand() ) << 15 ) + rand() ) % 1000000000 + 1;
}
struct Treap{
	int poz, val, pri, min_poz, max_poz, max_val;
	Treap *st, *dr;
	Treap( Treap *l, Treap *r, int pozitie, int valoare, int pr, int min_pozitie, int max_pozitie ){
		st = l;
		dr = r;
		poz = pozitie;
		val = valoare;
		pri = pr;
		min_poz = min_pozitie;
		max_poz = max_pozitie;
		max_val = val;
	}
};
Treap *NILL = new Treap( nullptr, nullptr, -1, -1e9, -1, 1e9, -1e9 );
void left_rotate( Treap*& nod ){
	Treap *aux = nod->dr;
	nod->dr = aux->st;
	aux->st = nod;
	nod = aux;
}
void right_rotate( Treap*& nod ){
	Treap *aux = nod->st;
	nod->st = aux->dr;
	aux->dr = nod;
	nod = aux;
}
void recheck( Treap*& nod ){
	if( nod == NILL ){
		return;
	}
	nod->max_val = nod->val;
	nod->max_val = max( nod->max_val, nod->st->max_val );
	nod->max_val = max( nod->max_val, nod->dr->max_val );
	nod->min_poz = min( nod->poz, nod->st->min_poz );
	nod->max_poz = max( nod->poz, nod->dr->max_poz );
}
void balance( Treap*& nod ){
	if( nod == NILL ){
		return;
	}
	if( nod->pri < nod->st->pri ){
		right_rotate( nod );
	}
	if( nod->pri < nod->dr->pri ){
		left_rotate( nod );
	}
	recheck( nod->st );
	recheck( nod->dr );
	recheck( nod );
}
void insert( Treap*& nod, int poz, int val ){
	if( nod == NILL ){
		nod = new Treap( NILL, NILL, poz, val, generate_rand(), poz, poz );
		return;
	}
	if( poz < nod->poz ){
		insert( nod->st, poz, val );
	}
	else{
		insert( nod->dr, poz, val );
	}
	balance( nod );
}
int max_query( Treap*& nod, int left, int right ){
	int max_st = -1e9, max_dr = -1e9, max_curr = -1e9;
	if( nod == NILL ){
		return -1e9;
	}
	if( left <= nod->min_poz && nod->max_poz <= right ){
		return nod->max_val;
	}
	if( left <= nod->poz && nod->poz <= right ){
		max_curr = nod->val;
	}
	if( left <= nod->st->max_poz ){
		max_st = max_query( nod->st, left, right );
	}
	if( nod->dr->min_poz <= right ){
		max_dr = max_query( nod->dr, left, right );
	}
	return max( max_curr, max( max_st, max_dr ) );
}
void erase( Treap*& nod, int poz ){
	if( nod == NILL ){
		return;
	}
	if( poz < nod->poz ){
		erase( nod->st, poz );
	}
	else if( poz > nod->poz ){
		erase( nod->dr, poz );
	}
	else{
		if( nod->st == NILL && nod->dr == NILL ){
			delete nod;
			nod = NILL;
		}
		else if( nod->st->poz < nod->dr->poz ){
			left_rotate( nod );
			erase( nod, poz );
		}
		else{
			right_rotate( nod );
			erase( nod, poz );
		}
	}
	balance( nod );
}
int main(){
	int n, m, i, val, x, y, tip;
	ifstream fin( "arbint.in" );
	ofstream fout( "arbint.out" );
	srand( 6565 );
	Treap *root = NILL;
	fin >> n >> m;
	for( i = 0; i < n; i++ ){
		fin >> val;
		insert( root, i, val );
		//cout << max_query( root, 1, 2 ) << '\n';
	}
	for( i = 0; i < m; i++ ){
		fin >> tip >> x >> y;
		x--;
		if( tip == 0 ){
			y--;
			fout << max_query( root, x, y ) << '\n';
		}
		else{
			erase( root, x );
			insert( root, x, y );
		}
		//cout << max_query( root, 1, 2 ) << '\n';
	}
	return 0;
}