#include <fstream>
#include <random>
#include <ctime>
#include <cmath>
using namespace std;
ifstream in("arbint.in");
ofstream out("arbint.out");
struct nya{
nya *st,*dr;
int val,prior,sz,mi;};
nya nil;
nya *tr=&nil;
nya* trr(nya *n,nya *f,int c)
{
    if (c==0) n->st=f;
    else n->dr=f;
    n->sz=1+n->st->sz+n->dr->sz;
    n->mi=n->val;
    if (n->st!=&nil) n->mi=max(n->mi,n->st->mi);
    if (n->dr!=&nil) n->mi=max(n->mi,n->dr->mi);
    return n;
}
pair<nya*,nya*> split(nya* n,int k)
{
    if (n==&nil) return {&nil,&nil};
    if (n->st->sz>=k) {auto t=split(n->st,k); return {t.first,trr(n,t.second,0)};}
    else {auto t=split(n->dr,k-n->st->sz-1); return {trr(n,t.first,1),t.second};}
}
nya* mer(nya* a,nya* b)
{
    if (a==&nil) return b;
    if (b==&nil) return a;
    if (a->prior>b->prior) {return trr(a,mer(a->dr,b),1);}
    else return trr(b,mer(a,b->st),0);
}
int main()
{
    mt19937 mt(time(nullptr));
    int n,q,z,x,y;
    int c;
    in>>n;
    in>>q;
    for (int i=1;i<=n;++i)
    {
        in>>z;
        tr=mer(tr,new nya{&nil,&nil,z,abs(mt()),1,z});
    }
    for (int i=1;i<=q;++i)
    {
        in>>c>>x>>y;
        if (c==0) {auto t=split(tr,y); auto t2=split(t.first,x-1); out<<t2.second->mi<<'\n'; tr=mer(mer(t2.first,t2.second),t.second);}
        else {auto t=split(tr,x-1); auto t2=split(t.second,1); t2.first->val=y; t2.first->mi=y; tr=mer(t.first,mer(t2.first,t2.second));}
    }
    return 0;
}