#include<fstream>
#include<iostream>
using namespace std;
long a,b,t[100001],n,m,c[100001];
void quic(int e,int v)
{
    if(e<v)
    {
        int i,j,k;
        k=t[(e+v)/2];
        i=e-1;
        j=v+1;
        while(i<j)
        {
            do j--;
            while(t[j]>k);
            do i++;
            while(t[i]<k);
            if(i<j)
            {
                swap(t[i],t[j]);
                swap(c[i],c[j]);
            }
        }
        quic(e,j);
        quic(j+1,v);
    }
}
int main()
{
    ifstream f("arbint.in");
    ofstream g("arbint.out");
    long i,j,d;
    bool p;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>t[i];
        c[i]=i;
    }
    quic(1,n);
    for(i=1;i<=m;i++)
    {
        f>>p>>a>>b;
        if(p)
        {
            j=1;
            while(c[j]!=a)
                j++;
            d=1;
            while(t[d]<b&&d<=n)
            d++;
            d--;
            if(j>d)
                while(j>d+1)
                {
                    c[j]=c[j-1];
                    t[j]=t[j-1];
                    j--;
                }
            else if(j<d)
                while(d>j)
                {
                    c[j]=c[j+1];
                    t[j]=t[j+1];
                    j++;
                }
            c[j]=a;
            t[j]=b;
        }
        else {
            j=n;
            while(!(c[j]<=b&&c[j]>=a))
                j--;
            g<<t[j]<<"\n";
        }
    }
    f.close();
    g.close();
    return 0;
}