#include <fstream>
using namespace std;
long long n,v[100020],up,down,mid,log;
int lo(int x)
{
    int poz=0;
    for(int i=log;i>=0;i--)
        if(poz+(1<<i)<=n && v[poz+(1<<i)]<x) poz+=1<<i;
    return poz+1;
}

int hi(int x)
{
    int poz=0;
    for(int i=log;i>=0;i--)
        if(poz+(1<<i)<=n && v[poz+(1<<i)]<=x) poz+=1<<i;
    return poz;
}

int main()
{
    long long h,i,j,k,a,b,m;
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>v[i];
    }
    fin>>m;
     for(log=1;(1LL<<log)<=n;log++);log--;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b;
       if(a==1)
       {
           fout<<hi(b)<<endl;
       }
       else if(a==2)
       {
           fout<<lo(b)<<endl;
       }
       else
       {
           h=hi(b);
           if(v[h]==b)
           {
               fout<<h<<endl;
           }
           else
           {
               fout<<"-1"<<endl;
           }
       }


    }
    return 0;
}