#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#define DIMMAX 100005
#define sqrt_DIMMAX 320
#define ll long long
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

using namespace std;

ll A[DIMMAX],op[DIMMAX][3];
ll N, M, rad;
ll smen[sqrt_DIMMAX];

void init()
{
    FOR(i,0,DIMMAX-5)
    {
        A[i]=-2;
    }
    FOR(i,0,sqrt_DIMMAX-2)
    {
        smen[i]=-3;
    }
}

void citire()
{
    ifstream f("arbint.in");
    f>>N>>M;
    FOR(i,1,N)
    {
        f>>A[i];
    }
    FOR(i,1,M)
    {
        FOR(j,0,2)
        {
            f>>op[i][j];
        }
    }
    f.close();
}

void afisare()
{
    FOR(i,1,N)
    {
        //cout<<A[i]<<" ";
    }
    cout<<'\n';
    FOR(i,1,rad)
    {
        cout<<smen[i]<<" ";
    }
    cout<<'\n'<<'\n';
}

ofstream g("arbint.out");

void build_smen(ll poz)
{
    int maxim=-10;
    FOR(i, (poz-1)*rad+1, poz*rad)
    {
        if(A[i]>maxim)
        {
            maxim=A[i];
        }
    }
    smen[poz]=maxim;
}

void parcurgere_a_1rad(ll &maxim, ll &i, ll poz)
{
     for(i = op[poz][1]; i % rad != 0 && i <= op[poz][2]; i++)
        maxim = max(maxim, A[i]);
}

void parcurgere_1rad_krad(ll &maxim, ll &i, ll poz)
{
    for(i ; op[poz][2] - i > rad; i += rad)
        maxim = max(maxim, smen[i+1 / rad]);
}

void parcurgere_krad_b(ll &maxim, ll &i, ll poz)
{
    for(i ; i <= op[poz][2]; i++)
        maxim = max(maxim, A[i]);
}

void rezolavare0(ll poz)
{
    ll maxim = -1;
    ll i;

    parcurgere_a_1rad(maxim, i, poz);

    parcurgere_1rad_krad(maxim, i, poz);

    parcurgere_krad_b(maxim, i, poz);

    g << maxim << '\n';
}

void rezolavare1(ll poz)
{
    A[op[poz][1]]=op[poz][2];
    smen[(poz+1)/rad]=-5;
    build_smen((poz+1)/rad);
}

int main()
{
    init();
    citire();
    rad=sqrt(N);
    if(rad*rad!=N)rad++;

    FOR(i,1,rad)
    build_smen(i);

    FOR(i,1,M)
    {
        if(op[i][0]==0)rezolavare0(i);
        else rezolavare1(i);
    }

    //afisare();

    g.close();
    return 0;
}