#include<fstream>
#include<vector>
#include<math.h>
using namespace std;

ifstream fin("arbint.in");
ofstream fout("arbint.out");

vector<int> tomb;
vector<int> legnagyobb_Tgy;

int n, m;
int gyok;

void masol(int poz, int ertek) {
	tomb[poz] = ertek;
	if (ertek > legnagyobb_Tgy[poz / gyok]) {
		legnagyobb_Tgy[poz / gyok] = ertek;
	}
	else {
		int kezdet = (poz / gyok) * gyok;
		int vege = kezdet + gyok - 1;
		int max = tomb[kezdet];
		for (int i = kezdet + 1; i <= vege; ++i)
			if (tomb[i] > max)
				max = tomb[i];
		legnagyobb_Tgy[poz / gyok] = max;
	}
}

int max(int kp, int vp) {
	int gyok_kezdet, gyok_veg;

	if (kp == (kp / gyok)*gyok)
		gyok_kezdet = kp / gyok;
	else
		gyok_kezdet = kp / gyok + 1;
	
	if (vp + 1 == ((vp + 1) / gyok)*gyok)
		gyok_veg = vp / gyok;				 //
	else
		gyok_veg = vp / gyok - 1;

	int maximum = tomb[kp];
	//szakaszokig
	for (int i = kp; i <= gyok_kezdet * gyok - 1; ++i)
		if (tomb[i] > maximum)
			maximum = tomb[i];
	//szakaszok kozott
	for (int i = gyok_kezdet; i <= gyok_veg; ++i)
		if (legnagyobb_Tgy[i] > maximum)
			maximum = legnagyobb_Tgy[i];
	//szakaszok utan
	for (int i = (gyok_veg + 1) * gyok; i <= vp; ++i)
		if (tomb[i] > maximum)
			maximum = tomb[i];

	return maximum;
}

int main() {
	fin >> n >> m;

	gyok = sqrt(n);

	legnagyobb_Tgy.resize(gyok + 1);
	fill(legnagyobb_Tgy.begin(), legnagyobb_Tgy.end(), -1);
	
	for (int i = 0; i < n; ++i) {
		int szam;
		fin >> szam;
		tomb.push_back(szam);
		if (szam > legnagyobb_Tgy[i / gyok])
			legnagyobb_Tgy[i / gyok] = szam;
	}

	for (int i = 0; i < m; ++i) {
		int elso, masodik, harmadik;
		fin >> elso >> masodik >> harmadik;
		masodik--;
		if (elso == 0)
			fout << max(masodik, harmadik - 1) << "\n";
		else
			masol(masodik, harmadik);
	}

	return 0;
}