#include <bits/stdc++.h>

using namespace std;

template <typename Type>
class Treap
{
    typedef struct _Node
    {
        Type key;
        Type maxim;
        size_t contor;
        size_t priority;
        _Node *l, *r;

        _Node( const Type _key, const size_t _priority, const size_t nr_nodes, _Node *st, _Node *dr )
        {
            key = _key;
            maxim = _key;
            priority = _priority;
            contor = nr_nodes;
            l = st;
            r = dr;
        }

        void update()
        {
            this->maxim = this->key;
            maxim = max( this->maxim, this->l->maxim );
            maxim = max( this->maxim, this->r->maxim );

            this->contor = 1;
            this->contor += this->l->contor;
            this->contor += this->r->contor;
        }

    } *Node;

    void rotateRight( Node &T )
    {
        Node aux = T->l;
        T->l = aux->r;
        aux->r = T;

        T->update();
        aux->update();

        T = aux;
    }

    void rotateLeft( Node &T )
    {
        Node aux = T->r;
        T->r = aux->l;
        aux->l = T;

        T->update();
        aux->update();

        T = aux;
    }

    void balance( Node &T )
    {
        if ( T->l->priority > T->priority )
            rotateRight( T );

        if ( T->r->priority > T->priority )
            rotateLeft( T );
    }

    void insert( Node &T, const size_t pos, const int key, size_t p = rand() % INF )
    {
        if ( T == NIL )
        {
            T = new _Node( key, p, 1, NIL, NIL );
        }
        else
        {
            if ( pos <= T->l->contor + 1 )
                insert( T->l, pos, key, p );
            else
                insert( T->r, pos - T->l->contor - 1, key, p );

            balance( T );
        }

        if ( T != NIL )
            T->update();
    }

    void erase( Node &T, const size_t pos )
    {
        if ( T == NIL ) return;

        if ( pos <= T->l->contor )
            erase( T->l, pos );
        else
            if ( pos > T->l->contor + 1 )
                erase( T->r, pos - T->l->contor - 1 );
            else
            {
                if ( T->l == NIL && T->r == NIL )
                {
                    delete T;
                    T = NIL;
                }
                else
                {
                    if ( T->l->priority > T->r->priority )
                    {
                        rotateRight( T );
                        erase( T->r, pos - T->l->contor - 1 );
                    }
                    else
                    {
                        rotateLeft( T );
                        erase( T->l, pos );
                    }
                }
            }

        if ( T != NIL )
            T->update();
    }

    void split( Node &root, Node &L, Node &R, const size_t pos )
    {
        insert( root, pos, 1, INF );
        L = root->l;
        R = root->r;
        delete root;
        root = NIL;
    }

    void merge( Node &root, Node &L, Node &R )
    {
        root = new _Node( 0, INF, 1, L, R );
        root->update();
        erase( root, root->l->contor + 1 );
    }

    Node root, NIL;
    const static int INF = 1e9;

    void print(Node T)
    {
        if ( T == NIL ) return;

        print( T->l );
        cerr << T->key << " ";
        print( T->r );
    }

public:

    Treap()
    {
        srand( time(NULL) );
        NIL = new _Node( -INF, 0, 0, NULL, NULL );
        root = NIL;
    }

    void insert( const size_t pos, const Type key )
    {
        insert( root, pos, key );
    }

    void erase( const size_t pos )
    {
        erase( root, pos );
    }

    Type query( size_t x, size_t y )
    {
        Type sol = 0;

        Node tmp, T1, T2, T3;

        split( root, T1, T2, y + 1 );
        split( T1, T3, tmp, x );

        sol = tmp->maxim;

        merge( T1, T3, tmp );
        merge( root, T1, T2 );

        return sol;
    }

    void update( const size_t x, const Type value )
    {
        erase( root, x );
        insert( root, x, value );
    }

    void print()
    {
        print( root );
    }
};



int main()
{
    FILE *f = fopen("arbint.in", "r");
    FILE *g = fopen("arbint.out", "w");

    int N, M, tip, a, b;
    Treap <int> T;

    fscanf(f, "%d %d\n", &N, &M);

    for ( int i = 1; i <= N; ++i )
    {
        fscanf(f, "%d ", &a);
        T.insert( i, a );
    }

    while ( M-- )
    {
        fscanf(f, "%d %d %d\n", &tip, &a, &b);

        if ( tip == 0 )
            fprintf(g, "%d\n", T.query( a, b ) );
        else
            T.update( a, b );
    }

    return 0;
}