#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
const char iname[] = "arbint.in";
const char oname[] = "arbint.out";
ifstream fin(iname);
ofstream fout(oname);
int N, M, a, b, cod_op;
struct bucket{
	int v, g_ind;
}v[100004];
struct up2date{
	int mv;
	int st, dr;
}G[10004];
void read (){
	int rad, nrg = 1, bucket_max = 0, last_dr;
	fin >> N >> M; rad = sqrt(1.0 * N);
	for (int i = 1, j = 1; i <= N; ++i, ++j)
	{
		fin >> v[i].v; v[i].g_ind = nrg;
		bucket_max = max(bucket_max, v[i].v);
		if (j == rad)
		{
			G[nrg].mv = bucket_max;
			G[nrg].dr = i; last_dr = i;
			G[nrg].st = i - rad + 1;
			bucket_max = 0, j = 0, ++nrg;
		}
	}
	G[nrg].st = last_dr; G[nrg].dr = N;
	for (int i = last_dr + 1; i <= N; ++i)
		bucket_max = max(bucket_max, v[i].v);
	G[nrg].mv = bucket_max;
}
inline void update (int poz, int x){
	v[poz].v = x; 
	int bucket_max = 0;
	int i = v[poz].g_ind, j;
	for (j = G[i].st; j <= G[i].dr; ++j)
		bucket_max = max(bucket_max, v[j].v);
	G[i].mv = bucket_max;
}
inline int query (int x, int y)
{
	int ind_dr, ind_st, i, Q_ANS = 0, mxv = 0;
	ind_st = v[x].g_ind; ind_dr = v[y].g_ind;
	for (i = y; i >= G[ind_dr].st; --i)
		mxv = max(mxv, v[i].v);
	for (i = x; i <= G[ind_st].dr; ++i)
		mxv = max(mxv, v[i].v);
	Q_ANS = max(Q_ANS, mxv);
	ind_st += 1; ind_dr -= 1;
	for (i = ind_st; i <= ind_dr; ++i)
		Q_ANS = max(Q_ANS, G[i].mv);
	return Q_ANS;
}
int main()
{
	read();
	while (M--)
	{
		fin >> cod_op; 
		if (cod_op){
			fin >> a >> b; 
			update(a, b);
		}
		else{
			fin >> a >> b;
			fout << query(a, b) << '\n';
		}
	}
	return 0;
}