#include <iostream>
#include<cstdio>

using namespace std;
int v[100001],n,m,tip,valoare;

int f0(int stg, int drp, int valoare)
{


   if(stg == drp){ if(v[stg]==valoare)return stg; else return -1; }
    else{

        int mij=(stg+drp)/2+1;

        if(v[mij]<=valoare)return f0(mij,drp,valoare);

        else return f0(stg,mij-1,valoare);



    }

}
int f1(int stg,int drp,int valoare)
{


   if(stg == drp){ return stg;  }
    else{

        int mij=(stg+drp+1)/2;

        if(v[mij]>valoare)return f1(stg,mij-1,valoare);

        else return f1(mij,drp,valoare);



    }
}

int f2(int stg,int drp, int valoare)
{


   if(stg == drp){ return stg;  }
    else{

        int mij=(stg+drp)/2;

        if(v[mij]>=valoare)return f2(stg,mij,valoare);

        else return f2(mij+1,drp,valoare);



    }
}


int main()
{
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
cin>>n;
for(int i=1; i<=n; i++)cin>>v[i];
cin>>m;
for(int i=1; i<=m; i++)
{
    cin>>tip>>valoare;
    if(tip==0)cout<<f0(1,n,valoare)<<"\n";
    if(tip==1)cout<<f1(1,n,valoare)<<"\n";
    if(tip==2)cout<<f2(1,n,valoare)<<"\n";
}


    return 0;
}