#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 a,int b,int x,int y,int poz)
{
    arb[poz].push_back(a);
    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(a,b,nrBef,-1,nr);
        arb[nr].push_back(arb[nrBef][4]);
        y=nrBef;
        x=nr;
        nrBef=nr;
        nr++;

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

int gasire(int x,int i)
{
    //cout<<x;
    if(arb[x][5]==car)
        return arb[x][4];
    if(x==arb[arb[x][5]][i])
        return gasire(arb[x][5],i);
    return arb[x][4];
}

int cautare(int x,int y,int h)
{
    int a,b;
    a=gasire(sir[x],0);
    //cout<<'\n';
    b=gasire(sir[y],1);
    //cout<<'\n';
    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 afis()
{
    for(int i=0; i<n; i++)
        out<<arb[sir[i]][4]<<' ';
    out<<'\n';
}

void parcurgere(int x)
{
    out<<x<<' '<<arb[x][4]<<'\n';
    if(arb[x][2]!=-1)
        parcurgere(arb[x][2]);



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

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

void schimbare(int x,int y)
{
    int i;

    arb[sir[x]][4]=y;

    for(i=arb[sir[x]][5]; i!=car; i=arb[i][5])
        intre(i);

    intre(i);
}

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

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