#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,v[100001],m,i,a,x;
int cautB0(int st,int dr){
    int mij;
    if (st>dr) return -1;
    mij=st+(dr-st)/2;
    if (v[mij]==x && v[mij+1]!=x) return mij;
    if (x<v[mij]) return cautB0(st,mij-1);
      else
        return cautB0(mij+1,dr);
}
int cautB1(int st,int dr){
    int mij;
    mij=st+(dr-st)/2;
    if (st>dr) return n;
    if (v[mij]<=x && v[mij+1]>x) return mij;
    if (v[mij]>x) return cautB1(st,mij-1);
      else
        return cautB1(mij+1,dr);
}
int cautB2(int st,int dr){
     int mij;
     mij=st+(dr-st)/2;
     if (v[mij]>=x && v[mij-1]<x) return mij;
     if (v[mij]<x) return cautB2(mij+1,dr);
       else
        return cautB2(st,mij-1);
}
int main(){
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for (i=1;i<=m;i++)
    {
        fin>>a>>x;
        if (a==0) fout<<cautB0(1,n)<<'\n';
          else
            if (a==1) fout<<cautB1(1,n)<<'\n';
              else
                if (a==2) fout<<cautB2(1,n)<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}