/*
ID:piyushp1
LANG:C
TASK:treeinterval */
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int lend;
int rend;
int max;
int index;
struct Node *left;
struct Node *right;
}
node;
int glob=0;
int *a;
void segmentree(node *temp,int left,int right);
void findmax(node *temp);
int query(node *temp,int A,int B);
void update(node *temp,int index,int key);
int main()
{
FILE *fin,*fout;
fin=fopen("arbint.in","r");
fout=fopen("arbint.out","w");
int i,j,n,m;
fscanf(fin,"%d%d",&m,&n);
a=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
fscanf(fin,"%d",&a[i]);
int **op=(int**)malloc(sizeof(int*)*m);
for(i=0;i<m;i++)
{
op[i]=(int*)malloc(sizeof(int)*3);
fscanf(fin,"%d%d%d",&op[i][0],&op[i][1],&op[i][2]);
if(op[i][0]==0)
{
op[i][1]--;op[i][2]--;
}
else
op[i][1]--;
}
node *root=(node*)malloc(sizeof(node)*1);
root->lend=0;
root->rend=n-1;
root->max=-1;
root->left=NULL;root->right=NULL;
segmentree(root,0,n-1);
findmax(root);
// printf("%d %d\n",root->max,root->index);
for(i=0;i<m;i++)
{
if(op[i][0]==0)
{
j=query(root,op[i][1],op[i][2]);
fprintf(fout,"%d\n",j);
}
else
{
a[op[i][1]]=op[i][2];
update(root,op[i][1],op[i][2]);
}
}
// printf("printing preoder\n");
// preorder(root);
return(0);
}
int query(node *temp,int A,int B)
{
int i,j,max,div;
if(temp->lend==A && temp->rend==B)
return(temp->max);
div=(temp->lend+temp->rend)/2;
if(A>=temp->lend && B<=div )
return(query(temp->left,A,B));
if(A>div && B<=temp->rend)
return(query(temp->right,A,B));
if(A<=div && A >=temp->lend && B>div && B<=temp->rend)
{
if(A==temp->lend )
i=temp->left->max;
else
i=query(temp->left,A,div);
if(B==temp->rend)
j=temp->right->max;
else
j=query(temp->right,div+1,B);
if(i>j)
return(i);
else
return(j);
}
}
void update(node *temp,int index,int key)
{
int i,j,div=(temp->lend+temp->rend)/2;
if(temp->lend==temp->rend)
{
temp->max=key;
temp->index=index;
return;
}
if(index>div)
update(temp->right,index,key);
else
update(temp->left,index,key);
if(a[temp->left->index]>a[temp->right->index])
{
temp->max=a[temp->left->index];
temp->index=temp->left->index;
}
else
{
temp->max=a[temp->right->index];
temp->index=temp->right->index;
}
}
void findmax(node *temp)
{
int max;
if(temp->max!=-1)
return;
if(temp->right==NULL && temp->left==NULL)
return;
else if(temp->right->max!=-1 && temp->left->max!=-1 )
{
if(a[temp->left->index]>a[temp->right->index])
{
temp->max=a[temp->left->index];
temp->index=temp->left->index;
}
else
{
temp->max=a[temp->right->index];
temp->index=temp->right->index;
}
return;
}
else
{
findmax(temp->left);
findmax(temp->right);
if(a[temp->left->index]>a[temp->right->index])
{
temp->max=a[temp->left->index];
temp->index=temp->left->index;
}
else
{
temp->max=a[temp->right->index];
temp->index=temp->right->index;
}
}
}
void segmentree(node *temp,int left,int right)
{
node *temp1,*temp2;
if(left==right)
{
temp->left=NULL;temp->right=NULL;
temp->max=a[left];
temp->index=left;
return;
}
else
{
temp->left=(node*)malloc(sizeof(node)*1);
temp->right=(node*)malloc(sizeof(node)*1);
temp1=temp->left;
temp2=temp->right;
temp1->max=-1;
temp2->max=-1;
temp1->lend=left;temp1->rend=(left+right)/2;
temp2->lend=(left+right)/2+1;temp2->rend=right;
segmentree(temp1,temp1->lend,temp1->rend);
segmentree(temp2,temp2->lend,temp2->rend);
}
}