#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main()
{ int i,j,n,intre,y,x,st,dr,m,gasit,a[100000];
in>>n;

for(i=1;i<=n;i++){
in>>a[i];
}
in>>intre;
for(j=1;j<=intre;j++){
in>>y>>x;
switch(y){
    case 0:{st=1; dr=n; gasit=0;
            while (st<=dr && gasit!=1) {
            m=(st+dr)/2;
            if(a[m]==x&&a[m+1]>x) gasit=1;
                        else if(x<a[m]) dr=m-1;
                                    else st=m+1;
                }
            if(st>dr) out<<-1<<endl;
                else out<<m<<endl;
                break;
    }

    case 1:{st=1; dr=n; gasit=0;
            while (st<=dr && gasit!=1) {
            m=(st+dr)/2;
            if(a[m]<=x&&a[m+1]>x) gasit=1;
                        else if(x<a[m]) dr=m-1;
                                    else st=m+1;
                }
            out<<m<<endl;
            break;
    }

    case 2:{st=1; dr=n; gasit=0;
            while (st<=dr && gasit!=1) {
            m=(st+dr)/2;
            if(a[m]>=x&&a[m-1]<x) gasit=1;
                        else if(x<=a[m]) dr=m-1;
                                   else st=m+1;
                }
            out<<m<<endl;
            break;
    }
}

}
in.close(); out.close();
}