#include <bits/stdc++.h>

using namespace std;

const int Nmax = 100000 + 1;

struct Node
{
    int maxim;
    Node *l, *r;

    explicit Node() : maxim(0), l(NULL), r(NULL) {
    }
};

Node *roots[Nmax];
int v[Nmax];
int N, M;

Node* build(int st, int dr)
{
    Node *node = new Node();

    if (st == dr)
        node->maxim = v[st];
    else
    {
        int m = (st + dr) / 2;

        node->l = build(st, m);
        node->r = build(m + 1, dr);

        node->maxim = max(node->l->maxim, node->r->maxim);
    }

    return node;
}

Node* create(Node *root, int st, int dr, int pos, int key)
{
    Node *node = new Node();

    if (st == dr)
        node->maxim = key;
    else
    {
        int m = (st + dr) / 2;

        if (pos <= m)
            node->l = create(root->l, st, m, pos, key);
        else
            node->l = root->l;

        if (m < pos)
            node->r = create(root->r, m + 1, dr, pos, key);
        else
            node->r = root->r;

        node->maxim = max(node->l->maxim, node->r->maxim);
    }

    return node;
}

int query(Node *root, int st, int dr, int st_q, int dr_q)
{
    if (st_q <= st && dr <= dr_q)
        return root->maxim;
    else
    {
        int m = (st + dr) / 2;
        int sol = numeric_limits<int>::min();

        if (st_q <= m)
            sol = max(sol, query(root->l, st, m, st_q, dr_q));

        if (m < dr_q)
            sol = max(sol, query(root->r, m + 1, dr, st_q, dr_q));

        return sol;
    }
}

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

    in >> N >> M;

    for (int i = 1; i <= N; ++i)
        in >> v[i];

    roots[0] = build(1, N);
    int currentRoot = 0;

    for (int i = 1; i <= M; ++i)
    {
        int tip, a, b;
        in >> tip >> a >> b;

        if (tip == 0)
            out << query(roots[currentRoot], 1, N, a, b) << "\n";
        else
        {
            roots[currentRoot + 1] = create(roots[currentRoot], 1, N, a, b);
            currentRoot++;
        }
    }

    return 0;
}