#include <bits/stdc++.h>

using namespace std;
ifstream f("arbint.in");
ofstream g("arbint.out");
const int Mod = 100000;
struct Node
{
    Node *st,*dr;
    int val,Max,prior,sz;
};
Node nil;
Node *Treap = &nil;
Node *mod_fiu(Node *nod, int care, Node *son)
{
    if(care==0)
    {
        nod->st = son;
    }
    else
    {
        nod->dr = son;
    }
    nod->sz = nod->st->sz + 1 + nod->dr->sz;
    nod->Max = max(nod->val,max(nod->st->Max,nod->dr->Max));
    return nod;
}
Node* join(Node *st, Node *dr)
{
    if(st==&nil)
    {
        return dr;
    }
    if(dr==&nil)
    {
        return st;
    }
    if(st->prior>=dr->prior)
    {
        return mod_fiu(st,1,join(st->dr,dr));
    }
    else
    {
        return mod_fiu(dr,0,join(st,dr->st));
    }
}
pair<Node*,Node*> split(Node *nod, int k)
{
    if(nod==&nil)
    {
        return {&nil,&nil};
    }
    if(nod->st->sz>=k)
    {
        auto t = split(nod->st,k);
        return {t.first,mod_fiu(nod,0,t.second)};
    }
    else
    {
        auto t = split(nod->dr,k - nod->st->sz - 1);
        return {mod_fiu(nod,1,t.first),t.second};
    }
}
Node *Add(int val)
{
    return join(Treap,new Node{&nil,&nil,val,val,rand()%Mod,1});
}
Node *query(int a, int b)
{
    auto t = split(Treap,b);
    auto t2 = split(t.first,a-1);
    g<<t2.second->Max<<'\n';
    return join(join(t2.first,t2.second),t.second);
}
Node *update(int poz, int val)
{
    auto t = split(Treap,poz);
    auto t2 = split(t.first,poz-1);
    t2.second->val = val;
    t2.second->Max = val;
    return join(join(t2.first,t2.second),t.second);
}
int main()
{
    int n,m;
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        f>>x;
        Treap = Add(x);
    }
    for(int i=1;i<=m;i++)
    {
        int t,a,b;
        f>>t>>a>>b;
        if(t==0)
        {
            Treap = query(a,b);
        }
        else
        {
            Treap = update(a,b);
        }
    }
    return 0;
}