#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) ((a) > (b) ? a : b)
typedef struct nod_t
{
int limleft, limright, val;
struct nod_t *right, *left;
} nod;
nod *createNod(int *vec, int start, int stop)
{
if (start == stop)
{
nod *ret = (nod *)malloc(sizeof(nod));
ret->limleft = start;
ret->limright = stop;
ret->right = NULL;
ret->left = NULL;
ret->val = vec[start];
return ret;
}
int mid = start + (stop - start) / 2;
nod *ret = (nod *)malloc(sizeof(nod));
ret->limleft = start;
ret->limright = stop;
ret->left = createNod(vec, start, mid);
ret->right = createNod(vec, mid + 1, stop);
ret->val = ret->left->val * (ret->left->val > ret->right->val) + ret->right->val * (ret->right->val > ret->left->val);
return ret;
}
void updateNod(int pos, int val, nod *arb)
{
if (arb->limleft == arb->limright)
{
arb->val = val;
return;
}
int mid = (arb->limleft + arb->limright) / 2;
if (pos <= mid)
{
updateNod(pos, val, arb->left);
}
else
{
updateNod(pos, val, arb->right);
}
arb->val = arb->left->val * (arb->left->val > arb->right->val) + arb->right->val * (arb->right->val > arb->left->val);
}
int intvMax(nod *arb, int strInt, int endInt)
{
if (arb->limright == strInt && arb->limleft == endInt)
{
return arb->val;
}
int min = (arb->limleft + arb->limright) / 2;
if (endInt <= min)
{
return intvMax(arb->left, strInt, endInt);
}
else if (strInt > min)
{
return intvMax(arb->right, strInt, endInt);
}
else
{
int max1 = intvMax(arb->left, strInt, min);
int max2 = intvMax(arb->right, min + 1, endInt);
return MAX(max1, max2);
}
}
int main()
{
int n = 0, m = 0, c = 0;
FILE *file = fopen("arbint.in", "rb");
FILE *fout = fopen("arbint.out", "wb");
fscanf(file, "%d", &n);
fscanf(file, "%d", &m);
int *vec = malloc(n * sizeof(int));
while (n)
{
fscanf(file, "%d", &vec[c]);
++c;
n -= 1;
}
nod *arb = createNod(vec, 0, c - 1);
int opt, par1, par2;
while (m)
{
fscanf(file, "%d", &opt);
fscanf(file, "%d", &par1);
fscanf(file, "%d", &par2);
if (opt == 0)
{
fprintf(fout, "%d\n", intvMax(arb, par1 - 1, par2 - 1));
}
else
{
updateNod(par1 - 1, par2, arb);
}
m--;
}
fclose(fout);
fclose(file);
return 0;
}