#include <iostream>
#include <vector>
#include <cassert>
#include <fstream>
using namespace std;

class arbint_iterativ{
    int n;
    vector<int> buf;
public:
    arbint_iterativ(vector<int>& vv): n(vv.size()), buf(2*n){
        for(int i = n; i < 2*n; ++i) buf[i] = vv[i];
        for(int i = n-1; i; --i) buf[i] = max(buf[2*i], buf[2*i+1]); }
    void update(int poz, int delta){
        for(buf[poz += n] = delta, poz/=2; poz; poz /= 2)
            buf[poz] = max(buf[2*poz], buf[2*poz+1]); }
    int query(int st, int dr){
        int rez = 0;
        for(st += n, dr += n+1; st < dr; st/=2, dr/=2){
            if(st%2) rez = max(rez, buf[st++]);
            if(dr%2) rez = max(rez, buf[--dr]); }
        return rez; } };


#define MAXN 131072
#define MINUS_INF 0
// == 2 ^ 17

int sir[MAXN] = {};

struct nod {
    nod *fiu_st, *fiu_dr;
    int st, dr, max; };

nod *build_arb(int st, int dr){
    // construieste un arbore care reprezinta subsecventa [st, dr]
    nod * rez = new nod;

    rez->st = st;
    rez->dr = dr;

    if(st == dr){
        rez->fiu_st = rez->fiu_dr = 0;
        rez->max = sir[st];
    }
    else{
        const int mij = (st+dr)/2;
        rez->fiu_st = build_arb(st, mij);
        rez->fiu_dr = build_arb(mij+1, dr);
        rez->max = max(rez->fiu_st->max, rez->fiu_dr->max);
    }
    return rez;
}

void schimba_valoare(nod *n, int poz, int val){
    assert(n->st <= poz && poz <= n->dr);
    if(n->st == n->dr){
        n->max = val;
        sir[poz] = val;
    }
    else{
        const int mij = (n->st+n->dr)/2;
        if(poz <= mij)
            schimba_valoare(n->fiu_st, poz, val); 
        else
            schimba_valoare(n->fiu_dr, poz, val);
        n->max = max(n->fiu_st->max, n->fiu_dr->max);
    }
}

int query_maxim(nod *n, int qst, int qdr){
    if(qst <= n->st && n->dr <= qdr) return n->max;
    if(n->dr < qst || qdr < n->st) return MINUS_INF;
    return max(query_maxim(n->fiu_st, qst, qdr),
        query_maxim(n->fiu_dr, qst, qdr));
}


void normalize(vector<int>& in){
    vector<int> sorted = in;
    sort(begin(sorted), end(sorted));
    for(int i = 0; i < in.size(); ++i){
        in[i] = lower_bound(begin(sorted), end(sorted), in[i]) - begin(sorted); } }

int main(){
    vector<int> v = {1, 100, 100, 1000 };
    normalize(v);
    for(auto& x : v) cout << x << ' ';


    ifstream f("arbint.in");
    ofstream g("arbint.out");
    int n, m;

    f >> n >> m;

    for(int i = 1; i <= n; ++i)
        f >> sir[i];

    nod *radacina = build_arb(1, MAXN);

    for(int i = 1, x, y, z; i <= m; ++i){
        f >> x >> y >> z;
        if(x == 0) g << query_maxim(radacina, y, z) << '\n';
        else schimba_valoare(radacina, y, z);
    }

    return 0;
}

/*
pentru subsir crescator maximal nlogn

d[i][j] = subsirul crescator maximal care incepe la o pozitite >= i,
    si ai carei prima valoarea este j

trecem de la i+1 la i avem o singura schimbare:
d[i][v[i]] = max(d[i+1][v[i]], 1 + d[i+1][>=v[i]])

OPTIMIZARE 1:
tinem doar un rand odata --> di[j] = d[i][j]

OPTIMIZARE 2:
observam ca trecerea de la di+1 la di include un query maxim pe subsecventa,
si o updatare de pozitie -- care se face cu arbint in log

=> se rezolva in nlogn


DATORII -- scadem dintr-o pozitie
           interogam un interval

pentru update de secventa si query de interval:
    update-ul nostru pana acum -> gaseste un drom
    query-ul nostru pana acum -> gaseste niste subsecvente

definim valoarea unui nod ca fiind suma valorilor de la radacina la el
    query-ul nostru devine -> update-ul vechi
    update-ul nostru nou devine -> query-ul vechi doar ca schimba starea

ceva de genul:

void update_secv(nod *n, int qst, int qdr, const int delta){
    if(qst <= n->st && n->dr <= qdr) n->sum += delta;
    if(n->dr < qst || qdr < n->st) ;
    update_secv(n->fiu_st, qst, qdr, delta);
    update_secv(n->fiu_dr, qst, qdr, delta);
}

sequence_query:

struct info{
    int best_atinge_st, best_atinge_dr, suma, best; };

info combine(info& st, info& dr){
    info rez;
    rez.best_atinge_st = max(st.best_atinge_st, st.suma + dr.best_atinge_st);
    rez.best_atinge_dr = max(dr.best_atinge_dr, dr.suma + st.best_atinge_dr);
    rez.suma = st.suma + dr.suma;
    rez.best = max(st.best_atinge_dr + dr.best_atinge_st, max(st.best, dr.best));
    return rez; }

info query_maxim(nod *n, int qst, int qdr){
    if(qst <= n->st && n->dr <= qdr) return n->informatie;
    info minus_inf = {};
    if(n->dr < qst || qdr < n->st) return minus_inf;
    return combine(query_maxim(n->fiu_st, qst, qdr),
        query_maxim(n->fiu_dr, qst, qdr));
}