#include <bits/stdc++.h>

using namespace std;

class Node
{
public:

    int Key;
    size_t Size;
    bool Reverse;
    size_t Priority;

    int Max;

    Node *Left, *Right;

    /// Key / Size / Reverse / Priority / Left / Right
    Node(const int k, const size_t nr, const bool rev, const size_t pr, Node *l, Node *r) : Key(k), Size(nr),
        Reverse(rev), Priority(pr), Max(k), Left(l), Right(r) {
    }
};

Node* NIL = new Node(0, 0, 0, 0, nullptr, nullptr); ///dummy node

///Auxilary functions for nodes-------------------------------------------
inline void lazy_update(Node* &T)
{
    if (T != NIL && T->Reverse == true)
    {
        T->Left->Reverse  ^= 1;
        T->Right->Reverse ^= 1;
        T->Reverse = false;

        swap(T->Left, T->Right);
    }
}

inline void update(Node* &T)
{
    lazy_update(T);
    lazy_update(T->Left);
    lazy_update(T->Right);

    if (T != NIL)
    {
        T->Size = 1 + T->Left->Size + T->Right->Size;
        T->Max = max(T->Key, max(T->Left->Max, T->Right->Max));
    }
}
///-------------------------------------------------------------------------

class IndexableTreap ///1-based
{
private:

    static const int MAX_PRIORITY = 2000000000;

    Node* rotate_to_right(Node* &T)
    {
        assert(T != NIL);

        Node *tmp = T->Left;
        T->Left = tmp->Right;
        tmp->Right = T;

        update(T);
        update(tmp);

        return tmp;
    }

    Node* rotate_to_left(Node* &T)
    {
        assert(T != NIL);

        Node *tmp = T->Right;
        T->Right = tmp->Left;
        tmp->Left = T;

        update(T);
        update(tmp);

        return tmp;
    }

    void balance(Node* &T)
    {
        assert(T != NIL);

        if (T->Left->Priority > T->Priority)
            T = rotate_to_right(T);
        else if (T->Right->Priority > T->Priority)
                T = rotate_to_left(T);
        else
            update(T);
    }

    void insert_after(Node* &T, size_t position, const int key, const int priority)
    {
        if (T == NIL)
            T = new Node(key, 1, false, priority, NIL, NIL);
        else
        {
            lazy_update(T);
            lazy_update(T->Left);
            lazy_update(T->Right);

            if (position <= T->Left->Size)
                insert_after(T->Left, position, key, priority);
            else
                insert_after(T->Right, position - 1 - T->Left->Size, key, priority);

            balance(T);
        }
    }

    void change_key(Node* &T, size_t position, const int key)
    {
        assert(T != NIL);

        lazy_update(T);
        lazy_update(T->Left);
        lazy_update(T->Right);

        if (T->Left->Size + 1 == position)
        {
            T->Key = key;
            update(T);
        }
        else
        {
            if (position <= T->Left->Size)
                change_key(T->Left, position, key);
            else
                change_key(T->Right, position - 1 - T->Left->Size, key);
        }

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

    int kth_element(Node* &T, size_t position)
    {
        assert(T != NIL);

        lazy_update(T);
        lazy_update(T->Left);
        lazy_update(T->Right);

        if (T->Left->Size + 1 == position)
            return T->Key;

        if (position <= T->Left->Size)
            return kth_element(T->Left, position);
        else
            return kth_element(T->Right, position - 1 - T->Left->Size);
    }

    void erase(Node* &T, size_t position)
    {
        if (T == NIL)
            return;

        lazy_update(T);
        lazy_update(T->Left);
        lazy_update(T->Right);

        if (position <= T->Left->Size)
            erase(T->Left, position);
        else if (position > T->Left->Size + 1)
            erase(T->Right, position - 1 - T->Left->Size);
        else
        {
            if (T->Left == NIL && T->Right == NIL)
            {
                delete T;
                T = NIL;
            }
            else
            {
                if (T->Left->Priority > T->Right->Priority)
                {
                    T = rotate_to_right(T);
                    erase(T->Right, position - 1 - T->Left->Size);
                }
                else
                {
                    T = rotate_to_left(T);
                    erase(T->Left, position);
                }
            }
        }

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

    void split(Node* &T, Node* &L, Node* &R, const size_t position) ///splits in [1...position] and [position+1...treap.size()]
    {
        insert_after(T, position, 1, MAX_PRIORITY);
        L = T->Left;
        R = T->Right;

        delete T;
        T = NIL;
    }

    void join(Node* &T, Node* &L, Node* &R)
    {
        T = new Node(1, 1, false, MAX_PRIORITY, L, R);
        update(T);

        erase(T, T->Left->Size + 1);
    }

    void inorder(Node* &T, vector<int> &keys)
    {
        if (T == NIL)
            return;

        lazy_update(T);
        lazy_update(T->Left);
        lazy_update(T->Right);

        inorder(T->Left, keys);
        keys.push_back(T->Key);
        inorder(T->Right, keys);
    }

    void clear(Node* &T)
    {
        if (T == NIL)
            return;

        clear(T->Left);
        clear(T->Right);

        assert(T != nullptr);

        delete T;
        T = NIL;
    }

public:

    Node *Root;

    IndexableTreap() : Root(NIL)
    {
    }

    IndexableTreap(IndexableTreap &IT) : Root(NIL)
    {
        for (size_t i = 1; i <= IT.size(); ++i)
        {
            int key = IT.kth_element(i);
            this->insert_after(i - 1, key);
        }
    }

    IndexableTreap& operator = (IndexableTreap &IT)
    {
        Root = NIL;

        for (size_t i = 1; i <= IT.size(); ++i)
        {
            int key = IT.kth_element(i);
            this->insert_after(i - 1, key);
        }

        return *this;
    }

    ///Modifiers ----------------------------------------------------------------------
    void insert_after(const size_t position, const int key) ///inserts after position
    {
        assert(position <= this->size());

        insert_after(Root, position, key, rand() % (MAX_PRIORITY - 2) + 1);
    }

    void erase(const size_t position)
    {
        assert(1 <= position);
        assert(position <= this->size());

        erase(Root, position);
    }

    void change_key(const size_t position, const int key)
    {
        assert(1 <= position);
        assert(position <= this->size());

        change_key(Root, position, key);
    }

    void push_back(const int key)
    {
        insert_after(this->size(), key);
    }

    void push_front(const int key)
    {
        insert_after(0U, key);
    }

    void pop_back()
    {
        assert(this->size() > 0);

        erase(this->size());
    }

    void pop_front()
    {
        assert(this->size() > 0);

        erase(1U);
    }

    void clear()
    {
        clear(Root);
    }
    ///---------------------------------------------------------------------------------

    void split(IndexableTreap &L, IndexableTreap &R, const size_t position)
    {
        L.clear();
        R.clear();

        split(this->Root, L.Root, R.Root, position);

        this->Root = NIL;
    }

    void join(IndexableTreap &L, IndexableTreap &R)
    {
        this->clear();

        join(this->Root, L.Root, R.Root);

        L.Root = NIL;
        R.Root = NIL;
    }

    void reverse(const size_t start, const size_t finish)
    {
        assert(1 <= start);
        assert(start <= finish);
        assert(finish <= this->size());

        Node *tmp, *T1, *T2, *T3;

        split(this->Root, tmp, T3, finish); ///tmp = [1...finish] | T3 = [finish+1...treap.size()]
        split(tmp, T1, T2, start - 1);      ///T1 = [1...start-1] | T2 = [start...finish]

        T2->Reverse = true;

        join(tmp, T1, T2);
        join(this->Root, tmp, T3);
    }

    size_t query(const size_t start, const size_t finish)
    {
        assert(1 <= start);
        assert(start <= finish);
        assert(finish <= this->size());

        Node *tmp, *T1, *T2, *T3;

        split(this->Root, tmp, T3, finish);
        split(tmp, T1, T2, start - 1);

        size_t Max = T2->Max;

        join(tmp, T1, T2);
        join(this->Root, tmp, T3);

        return Max;
    }

    ///Element access --------------------------------------------------------------------------
    int kth_element(const size_t position)
    {
        assert(1 <= position);
        assert(position <= this->size());

        return kth_element(Root, position);
    }

    int at(const size_t position)
    {
        return kth_element(position);
    }

    int operator [] (const size_t position)
    {
        return kth_element(position);
    }

    int front()
    {
        assert(this->empty() == false);

        return kth_element(1);
    }

    int back()
    {
        assert(this->empty() == false);

        return kth_element(this->size());
    }
    ///---------------------------------------------------------------------------------

    void inorder(vector<int> &keys)
    {
        inorder(Root, keys);
    }

    ///Capacity ------------------------------------------------------------------------
    size_t size() const
    {
        return Root->Size;
    }

    bool empty() const
    {
        return (Root->Size == 0);
    }
    ///---------------------------------------------------------------------------------
};

class Scanner
{
private:

    FILE *inputFile;
    int cursor;

    static const int MAX_SIZE = 1 << 16;
    char buffer[MAX_SIZE];

    inline char getChar()
    {
        if (cursor == MAX_SIZE)
        {
            cursor = 0;
            fread(buffer, MAX_SIZE, 1, inputFile);
        }

        return buffer[cursor++];
    }

    inline int getNr()
    {
        int a = 0;
        int sign = 1;
        char ch;

        do
        {
            ch = getChar();

        } while (!isdigit(ch) && ch != '-');

        if (ch == '-')
        {
            sign = -1;
            ch = getChar();
        }

        do
        {
            a = (a << 3) + (a << 1) + (ch - '0');
            ch = getChar();

        } while (isdigit(ch));

        return a * sign;
    }

public:

    Scanner() {
    }

    Scanner(const char *file)
    {
        inputFile = fopen(file, "r");
        cursor = MAX_SIZE;
    }

    inline Scanner& operator >> (int &x)
    {
        x = getNr();
        return *this;
    }
};

int main()
{
    Scanner in("arbint.in");
    ofstream out("arbint.out");

    int N, M;
    in >> N >> M;

    IndexableTreap Treap;

    for (int i = 1; i <= N; ++i)
    {
        int x;
        in >> x;

        Treap.push_back(x);
    }

    while (M--)
    {
        int tip, a, b;
        in >> tip >> a >> b;

        if (tip == 0)
            out << Treap.query(a, b) << "\n";
        else
            Treap.change_key(a, b);
    }

    return 0;
}