#include <bits/stdc++.h>
using namespace std;
ifstream fin("arbint.in");
ofstream fout("arbint.out");
int n, q;
vector<int> v;
const int NMAX=1e5;
int last=0;
struct persistent_seg{
    int ptr=0;
    struct Vertex{
        Vertex* left;
        Vertex* right;
        int val;
        Vertex():left(nullptr), right(nullptr), val(){}
        Vertex(int val):left(nullptr), right(nullptr),val(val){}
        Vertex(Vertex* l, Vertex* r):left(l), right(r), val(0){
            if(l){
                val=max(val, l->val);
            }
            if(r){
                val=max(val, r->val);
            }
        }
    };
    Vertex Node[12*NMAX+5];
    Vertex* T[NMAX+5];
    Vertex* new_vertex(int val){
        Node[ptr]=Vertex(val);
        return &Node[ptr++];
    }
    Vertex* new_vertex(Vertex* l, Vertex* r){
        Node[ptr]=Vertex(l, r);
        return &Node[ptr++];
    }
    Vertex* build(vector<int> &a, int left=1, int right=n){
        if(left==right){
            return new_vertex(a[left]);
        }
        int mid=(left+right)/2;
        return new_vertex(build(a, left, mid), build(a, mid+1, right));
    }
    Vertex* update(int poz, int val, Vertex* node, int left=1, int right=n){
        if(left==right){
            return new_vertex(val);
        }
        int mid=(left+right)/2;
        if(poz<=mid){
            return new_vertex(update(poz, val, node->left, left, mid), node->right);
        }else{
            return new_vertex(node->left, update(poz, val, node->right, mid+1, right));
        }

    }
    int query(int start, int finish, Vertex* node, int left=1, int right=n){
        if(start>right or finish<left){
            return 0;
        }
        if(start<=left and right<=finish){
            return node->val;
        }
        int mid=(left+right)/2;
        return max(query(start, finish, node->left, left, mid),query(start, finish, node->right, mid+1, right));
    }

};
persistent_seg seg;
int main(){
    fin>>n>>q;
    v.resize(n+1);
    for(int i=1;i<=n;i++){
        fin>>v[i];
    }
    seg.T[last]=seg.build(v);
    for(int i=1;i<=q;i++){
        int tip, a, b;
        fin>>tip>>a>>b;
        if(tip==0){
            fout<<seg.query(a, b, seg.T[last])<<'\n';
        }else{
            last++;
            seg.T[last]=seg.T[last-1];
            seg.T[last]=seg.update(a, b, seg.T[last]);
        }
    }
}