#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("arbint.in");
ofstream out("arbint.out");

vector<int> sir;
vector<vector<int> > arb;

int n,m,nr,nrBef,car;

void stocare()
{
    sir.resize(n+2);
    for(int i=0; i<n; i++)
        in>>sir[i];

}

void fac(int b,int x,int y,int poz)
{
    arb[poz].push_back(b);
    arb[poz].push_back(x);
    arb[poz].push_back(y);
}

void creare(int a,int b)
{
    //cout<<nr<<' ';
    int mij=(a+b)/2,x,y;
    if(a<b)
    {
        creare(a,mij);
        fac(mij,nrBef,-1,nr);
        arb[nr].push_back(arb[nrBef][3]);
        y=nrBef;
        x=nr;
        nrBef=nr;
        nr++;

        creare(mij+1,b);
        arb[x][2]=nrBef;
        arb[y].push_back(x);
        arb[nrBef].push_back(x);
        if(arb[x][3]<arb[nrBef][3])
            arb[x][3]=arb[nrBef][3];
        nrBef=x;
    }
    else
    {
        fac(a,-1,-1,nr);
        arb[nr].push_back(sir[a]);
        sir[a]=nr;
        x=nr;
        nrBef=nr;
        nr++;
    }
    car=x;
}

int cautare(int x,int y,int h)
{
    int a,b;
    if(y==x)
        return arb[sir[x]][3];
    if(x>arb[h][0])
        return cautare(x,y,arb[h][2]);
    if(y<=arb[h][0])
        return cautare(x,y,arb[h][1]);
    a=cautare(x,arb[h][0],arb[h][1]);
    b=cautare(arb[h][0]+1,y,arb[h][2]);
    if(a>b)
        return a;
    return b;
}

int impart(int a)
{
    int i,r=0;
    for(i=1; i<=a; i*=2)
        r+=i;
    r+=(a-i/2)*2;
    return r;
}

void intre(int i)
{
    if(arb[arb[i][1]][3]>arb[arb[i][2]][3])
        arb[i][3]=arb[arb[i][1]][3];
    else
        arb[i][3]=arb[arb[i][2]][3];
    //cout<<'*'<<arb[i][3]<<' ';
}

void afis()
{
    for(int i=0; i<n; i++)
        out<<arb[sir[i]][3]<<' ';
    out<<'\n';
}

void parcurgere(int x)
{
    if(arb[x][1]!=-1)
        parcurgere(arb[x][1]);

    out<<x<<' '<<arb[x][3]<<'\n';

    if(arb[x][2]!=-1)
        parcurgere(arb[x][2]);
}

void schimbare(int x,int y)
{
    int i;
    //cout<<sir[x];
    arb[sir[x]][3]=y;
    //cout<<'*'<<arb[sir[x]][3]<<' ';
    for(i=arb[sir[x]][4]; i!=car; i=arb[i][4])
    {
        //cout<<i;
        intre(i);
    }
    //cout<<i;
    intre(i);
    //cout<<'\n';
    //parcurgere(car);
    //afis();
}

int main()
{
    in>>n>>m;

    stocare();
    //cout<<impart(n);

    arb.resize(impart(n)+1);
    creare(0,n-1);
    //parcurgere(car);
    for(int i=0; i<m; i++)
    {
        int a,b,c;
        in>>c>>a>>b;
        if(c==0)
            out<<cautare(a-1,b-1,car)<<'\n';
        else
            schimbare(a-1,b);
    }
    return 0;
}