#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define NX 100010
#define SQRTNX 320
int a[NX], b[SQRTNX];

int max(int left, int right) 
{
	int max = a[left];
	for (int i = left + 1; i <= right; i++) 
	{
		if (max < a[i])
			max = a[i];
	}

	return max;
}

int sqrtMax(int left, int right, int sqrtN, int N)
{
	if (left - right < sqrtN) 
	{
		return max(left, right);
	}

	int bLeft = ceil((double)left / sqrtN);
	int bRight = ceil((double)right / sqrtN);
	int bLeftRem = left % sqrtN;
	int bRightRem = right % sqrtN; 
	int m = a[left] > a[right] ? a[left] : a[right];

	// left remainder
	if (left % sqrtN != 1) {

		m = max(left, (sqrtN - bLeftRem) + left + 1);
		bLeft++;
	}

	// right remainder
	if (right % sqrtN != 0) 
	{
		m = max(right - bRightRem, right);
		bRight--;
	}

	for (int i = bLeft; i <= bRight; i++)
	{
		if (m < b[i])
			m = b[i];
	}

	return m;
}

int main() 
{
	int N, M, op, an, bn, j = 1;
	freopen("arbint.in", "r", stdin);
	freopen("arbint.out", "w", stdout);

	scanf("%d %d", &N, &M);

	int sqrtN = sqrt((double)N);
	int left = 1;

	for (int i = 1; i <= N; i++) 
	{
		scanf("%d", &a[i]);
		if (i == N) 
		{
			b[j] = max(left, i);
			j++;
		}
		else {
			if (i % sqrtN == 0) {
				b[j] = max(left, i);
				j++;

				left = i + 1;
			}
		}
	}

	for (int i = 1; i <= M; i++)
	{
		scanf("%d %d %d\n", &op, &an, &bn);

		switch (op)
		{
		case 0:
			printf("%d\n", sqrtMax(an, bn, sqrtN, N));
			break;
		case 1:
			a[an] = bn;
			int bi = ceil((double)an / sqrtN);
			b[bi] = max(bi * sqrtN - sqrtN + 1, bi * sqrtN);
			break;
		}
	}
}