#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 * kMaxN];
	
 
	
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 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);
}