#include <fstream>
using namespace std;

ifstream fin; ofstream fout;
long n,m,a[100000],i,y; short x;

long bs1 (long x,long y,long z) {
     if (x==y)
        if (a[x]==z) return x; else return -1;
     else
         if (a[(x+y+1)/2]>z) return bs1 (x,(x+y-1)/2,z);
         else return bs1 ((x+y+1)/2,y,z);
}

long bs2 (long x,long y,long z) {
     if (x==y) return x;
     else
         if (a[(x+y+1)/2]>z) return bs1 (x,(x+y-1)/2,z);
         else return bs1 ((x+y+1)/2,y,z);
}


long bs3 (long x,long y,long z) {
     if (x==y) return x;
     else
         if (a[(x+y+1)/2]<=z) return bs1 (x,(x+y-1)/2,z);
         else return bs1 ((x+y+1)/2,y,z);
}

int main () {
    fin.open ("cautbin.in"); fout.open ("cautbin.out");
    fin>>n;
    for (i=0; i<n; i++) fin>>a[i];
    fin>>m;
    for (i=0; i<m; i++) {
        fin>>x>>y;
        if (x==0) fout<<bs1 (0,n-1,y)+1<<endl;
        if (x==1) fout<<bs2 (0,n-1,y)+1<<endl;
        if (x==2) fout<<bs3 (0,n-1,y)+1<<endl;
    }
    fin.close (); fout.close ();
    return 0;
}