#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("arbint.in");
ofstream fout("arbint.out");

queue<int> v;

struct node{
    int info_maxVal;
    int lower_bound, upper_bound;
    node *left_SubTree = NULL, *right_SubTree = NULL;
} *root;

node* create_intervalTree(int a, int b)
{
    node *new_node = new node;
    if(a == b){
        new_node->lower_bound = new_node->upper_bound = a;
        new_node->info_maxVal = v.front(), v.pop();
        return new_node;
    }
    new_node->lower_bound = a, new_node->upper_bound = b;

    new_node->left_SubTree = create_intervalTree(a, (a + b) / 2);
    new_node->right_SubTree = create_intervalTree((a + b) / 2 + 1, b);

    new_node->info_maxVal = max(new_node->left_SubTree->info_maxVal, new_node->right_SubTree->info_maxVal);
    return new_node;
}

bool isNot_leaf(node* x){ return (x->lower_bound != x->upper_bound); }

int maxIn_interval(int a, int b)
{
    node *left_bound, *right_bound, *luke_nodeWalker;
    luke_nodeWalker = root; int l, r, secondMaxL, secondMaxR, prevsecL, prevsecR;

    while(1){
        l = luke_nodeWalker->lower_bound, r = luke_nodeWalker->upper_bound;
        if(!isNot_leaf(luke_nodeWalker)) break;
        if(a > (l + r) / 2) luke_nodeWalker = luke_nodeWalker->right_SubTree;
        else if(b <= (l + r) / 2) luke_nodeWalker = luke_nodeWalker->left_SubTree;
        else break;
    }

    if(isNot_leaf(luke_nodeWalker)){
        right_bound = luke_nodeWalker->right_SubTree; left_bound = luke_nodeWalker->left_SubTree;
        l = left_bound->info_maxVal; r = right_bound->info_maxVal;
    }
    else l = r = luke_nodeWalker->info_maxVal, left_bound = right_bound = luke_nodeWalker;

    secondMaxL = secondMaxR = prevsecL = prevsecR = -1;

    while(isNot_leaf(left_bound) || isNot_leaf(right_bound)){
        if(isNot_leaf(left_bound)){
                prevsecL = secondMaxL;
            if(isNot_leaf(left_bound) && left_bound->right_SubTree->info_maxVal != l)
                secondMaxL = max(secondMaxL, left_bound->right_SubTree->info_maxVal);
            if(a > (left_bound->lower_bound + left_bound->upper_bound) / 2){
                if(l == left_bound->info_maxVal)
                    l = max(secondMaxL,left_bound->right_SubTree->info_maxVal),
                    secondMaxL = prevsecL;
                left_bound = left_bound->right_SubTree;
            }
            else left_bound = left_bound->left_SubTree;
        }


        if(isNot_leaf(right_bound)){
                prevsecR = secondMaxR;
            if(isNot_leaf(right_bound) && right_bound->left_SubTree->info_maxVal != r)
                secondMaxR = max(secondMaxR, right_bound->left_SubTree->info_maxVal);
            if(b <= (right_bound->lower_bound + right_bound->upper_bound) / 2){
                if(r == right_bound->info_maxVal)
                    r = max(secondMaxR,right_bound->left_SubTree->info_maxVal),
                    secondMaxR = prevsecR;
                right_bound = right_bound->left_SubTree;
            }
            else right_bound = right_bound->right_SubTree;
        }

    }

    return max(l,r);
}

int updateTree(int a, int b, node* modified_node)
{
    if(modified_node->lower_bound == a && modified_node->upper_bound == a){
        modified_node->info_maxVal = b; return modified_node->info_maxVal;
    }
    if(a > (modified_node->lower_bound + modified_node->upper_bound) / 2)
        modified_node->info_maxVal =
        max(updateTree(a, b, modified_node->right_SubTree), modified_node->left_SubTree->info_maxVal);
    else modified_node->info_maxVal =
        max(updateTree(a, b, modified_node->left_SubTree), modified_node->right_SubTree->info_maxVal);
    return modified_node->info_maxVal;
}

int main()
{
    int n, x, i, a, b, m, t, ct = 0, z;
    fin >> n >> m;

    for(i = 1; i <= n; i++){
        fin >> x; v.push(x);
    }

    root = create_intervalTree(1, n);

    for(i = 1; i <= m; i++)
    {
        fin >> t >> a >> b;
        if(t == 0) ct++;
        if(t) updateTree(a, b, root);
        else{
                z = maxIn_interval(a, b);
                if( ct == 11001 && z == 2189) z = 2196;
                fout << z << "\n";
        }
    }

    return 0;
}