#include <iostream>
	
#include <algorithm>
	
#include <bits/stdc++.h>
	
 
	
using namespace std;
	
 
	
#define bit(i) (i & -i)
	
#define dim 8192
	
#define sint int
	
char ax[dim];
	
int pz;
	
 
	
void cit(int &x) {
	
    x = 0;
	
    while (ax[pz] < '0' || ax[pz] > '9') 
	
        if (++pz == dim) fread(ax, 1, dim, stdin), pz = 0;
	
    while (ax[pz] >= '0' && ax[pz] <= '9') {
	
        x = x * 10 + ax[pz] - '0';
	
        if (++pz == dim) fread(ax, 1, dim, stdin), pz = 0;
	
    }
	
}
	
 
	
	
	
const int kMaxN = 100000;
	
	
	
const int kBuffSize = 655536;
	
	
	
 
	
	
	
#define fastcall __attribute__((optimize("-O3")))
	
	
	
#define inline __inline__ __attribute__((always_inline))
	
	
	
 
	
	
	
int T[2 ];
	
	
	
 
	
	
	
inline fastcall char getChar() {
	
	
	
    static char buff[kBuffSize];
	
	
	
    static int pos = kBuffSize;
	
	
	
 
	
	
	
    if (pos == kBuffSize) {
	
	
	
        fread(buff, 1, kBuffSize, stdin);
	
	
	
        pos = 0;
	
	
	
    }
	
	
	
    return buff[pos++];
	
	
	
}
	
	
	
 
	
	
	
inline fastcall int readInt() {
	
	
	
    int q = 0;
	
	
	
    char c;
	
	
	
    do {
	
	
	
        c = getChar();
	
	
	
    } while (!isdigit(c));
	
	
	
    do {
	
	
	
        q = (q << 1) + (q << 3) + (c - '0');
	
	
	
        c = getChar();
	
	
	
    } while (isdigit(c));
	
	
	
    return q;
	
	
	
}
	
	
	
 
	
	
	
char outBuff[kBuffSize];
	
	
	
int outPtr;
	
	
	
 
	
	
	
inline fastcall void putChar(const char &C) {
	
	
	
    outBuff[outPtr++] = C;
	
	
	
    if (outPtr == kBuffSize) {
	
	
	
        fwrite(outBuff, 1, kBuffSize, stdout);
	
	
	
        outPtr = 0;
	
	
	
    }
	
	
	
}
	
	
	
 
	
	
	
inline fastcall void writeInt(int X) {
	
	
	
    char digs[10];
	
	
	
    int n = 0, q;
	
	
	
    do {
	
	
	
        q = X / 10;
	
	
	
        digs[n++] = X - (q << 1) - (q << 3) + '0';
	
	
	
        X = q;
	
	
	
    } while (X);
	
	
	
    while (n--) {
	
	
	
        putChar(digs[n]);
	
	
	
    }
	
	
	
    putChar('\n');
	
	
	
}
	
 
	
const int N = 100001;
	
const int INF = 0;//0x3f3f3f3f;
	
sint a[N], aib1[N], aib2[N];
	
int n, m;
	
 
	
inline sint query(int left, int right)
	
{
	
	sint sol = INF;
	
	int i, j;
	
	for (i = left; i + bit(i) - 1 <= right; i += bit(i))
	
		sol = max(sol, aib2[i]);	
	
	
	
	for (j = right; j > 0 && j - bit(j) + 1 >= i; j -= bit(j))
	
		sol = max(sol, aib1[j]);
	
	
	
	if (i <= j)
	
		sol = max(sol, a[i]);
	
	return sol;
	
}
	
 
	
inline fastcall void extend(int &l, int &r, int &left, int &right, sint &minim)
	
{
	
	for (; r + bit(r) - 1 <= right; r += bit(r))
	
		if (minim < aib2[r])
	
			minim = aib2[r];
	
	for (; l > 0 && l - bit(l) + 1 >= left; l -= bit(l))
	
		if (minim < aib1[l])
	
			minim = aib1[l];
	
}
	
 
	
inline void update(int p, sint v)
	
{
	
	sint oldv = a[p];
	
	a[p] = v;
	
	int i, l, r, left, right;
	
	sint minim;
	
	l = p - 1; r = p + 1; minim = INF;
	
	sint vv;
	
	for (i = p; i <= n; i += bit(i))
	
	{
	
		vv = aib1[i];
	
		if (aib1[i] != oldv)
	
			aib1[i] = max(aib1[i], v);
	
		else
	
		{
	
			left = max(i - bit(i) + 1, 1);
	
			right = i;
	
			extend(l, r, left, right, minim);
	
			aib1[i] = max(v, max(a[left], max(a[right], minim)));
	
		}
	
 
	
		if (aib1[i] == vv)
	
			break;
	
	}
	
	
	
	l = p - 1; r = p + 1; minim = INF;
	
	for (i = p; i ; i -= bit(i))
	
	{
	
		vv = aib2[i];
	
		if (aib2[i] != oldv)
	
			aib2[i] = max(aib2[i], v);
	
		else
	
		{
	
			left = i;
	
			right = min(n, i + bit(i) - 1);
	
			extend(l, r, left, right, minim);
	
			aib2[i] = max(v, max(a[left], max(a[right], minim)));
	
		}
	
 
	
		if (aib2[i] == vv)
	
			break;
	
	}
	
}
	
 
	
void build()
	
{
	
	int i;
	
	for (i = 1; i <= n; ++i)
	
		aib1[i] = aib2[i] = a[i];
	
 
	
	for (i = 1; i <= n; ++i)
	
		if (i + bit(i) <= n)
	
			aib1[i + bit(i)] = max(aib1[i + bit(i)], aib1[i]);
	
 
	
	for (i = n; i ; --i)
	
		if (i - bit(i) > 0)
	
			aib2[i - bit(i)] = max(aib2[i - bit(i)], aib2[i]);
	
}
	
 
	
 
	
int tree[1];
	
	
	
 
	
	
	
void Build(){
	
	
	
    for (int i = n - 1; i; --i){
	
	
	
        tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
	
	
	
    }
	
	
	
}
	
	
	
void Update(int poz, int val)
	
	
	
{
	
	
	
    tree[poz += n] = val;
	
	
	
    for (poz >>= 1; poz >= 1; poz >>= 1)
	
	
	
        tree[poz] = max(tree[poz << 1], tree[poz << 1 | 1]);
	
	
	
}
	
	
	
 
	
	
	
int Query(int st, int dr)
	
	
	
{
	
	
	
    int res = 0;
	
	
	
    for (st += n, dr += n; st <= dr; st >>= 1, dr >>= 1){
	
	
	
        if (st & 1) res = max(res, tree[st++]);
	
	
	
        if (!(dr & 1)) res = max(res, tree[dr--]);
	
	
	
    }
	
	
	
    return res;
	
	
	
}
	
 
	
 
	
 
	
int main() {
	
    freopen("arbint.in", "r", stdin);
	
    freopen("arbint.out", "w", stdout);
	
    cit(n); cit(m);
	
    for (int i = 1; i <= n; ++i) {
	
        cit(a[i]);
	
    }
	
    build();
	
 
	
    int t, p, q;
	
    while (m--) {
	
        cit(t); cit(p); cit(q);
	
        if (t == 0) 
	
            writeInt(query(p, q));
	
            //cout << Query(p - 1, q - 1) << "\n";
	
        else 
	
            update(p, q);
	
    }
	
 
	
    fwrite(outBuff, 1, outPtr, stdout);
	
}