#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int a[100001],poz,u,n,p,st,dr,mij,x,ok,c,m,b[100001];
int main()
{   in>>n;
    for(int i=1;i<=n;i++)
  in>>a[i];
  in>>m;
  for(int j=1;j<=m;j++){
    in>>c>>x;
    if(c==0){
        st=1;dr=n;poz=-1;
        while(st<=dr){
            mij=(st+dr)/ 2;
            if(a[mij]==x) {poz=mij;st=mij+1;}
            else if(a[mij]>x) dr=mij-1;
            else st=mij+1;
        }
        b[j]=poz;
    }
    if(c==1){
            st=1;dr=n;poz=-1;
         while(st<=dr){
            mij=(st+dr)/2;
            if(a[mij]<=x) {poz=mij;st=mij+1;}
            else if(a[mij]>x) dr=mij-1;
        }
        b[j]=poz;

    }
    if(c==2){
        st=1;dr=n;poz=-1;
        while(st<=dr){
            mij=(st+dr)/2;
            if(a[mij]>=x) {poz=mij;dr=mij-1;}
            else st=mij+1;
        }
        b[j]=poz;
    }
  }
  for(int i=1;i<=m;i++) out<<b[i]<<endl;



    return 0;
}