#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)
{
int bLeft = ceil((double)left / sqrtN);
int bRight = ceil((double)N / sqrtN);
int max = a[left] > a[right] ? a[left] : a[right];
// left remainder
if (left % sqrtN != 1) {
for (int i = left + 1; i % sqrtN == 1 && i <= right; i++)
{
if (max < a[i])
max = a[i];
bLeft = i;
}
}
// right remainder
if (right % sqrtN != 0)
{
for (int i = right - 1; i % sqrtN == 0 && i >= left; i--)
{
if (max < a[i])
max = a[i];
bRight = i;
}
}
bLeft = ceil((double)bLeft / sqrtN);
bRight = ceil((double)bRight / sqrtN);
for (int i = bLeft; i <= bRight; i++)
{
if (max < b[i])
max = b[i];
}
return max;
}
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;
}
}
}