#include <iostream>
#include <fstream>;
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int i,n,m,q,x,st,dr,mid,V[100001],sol;
int main()
{fin>>n;
for(i=1;i<=n;i++)
    fin>>V[i];
fin>>m;
while(m!=0){
    m--;
    fin>>q>>x;
if(q==0){
    st=1;
    dr=n;
    sol=-1;
    while(st<=dr){
          mid=(st+dr)/2;
          if(x==V[mid]){
             while(V[mid]==x&&mid<=n)
                   mid++;
             sol=mid-1;
             break;
             }
          else
             if(x<V[mid])
                dr=mid-1;
             else
                st=mid+1;
    }
    fout<<sol<<'\n';
    continue;
}
if(q==1){
    st=1;
    dr=n;
    sol=-1;
    while(st<=dr){
           mid=(st+dr)/2;

             if(x<V[mid])
                dr=mid-1;
             else
             if(x>=V[mid]){
                 sol=mid;
                st=mid+1;
             }
    }
    fout<<sol<<'\n';
    continue;
}

    st=1;
    dr=n;
    sol=-1;
    while(st<=dr){
         mid=(st+dr)/2;

             if(x<=V[mid]){
                sol=mid;
                dr=mid-1;
             }
             else


                st=mid+1;
             }

    fout<<sol<<'\n';

}








    return 0;
}