#include<fstream>
#include<algorithm>
//#include<iostream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int a[100002];
int cautare(int N,int val,int x)
{
   int i,step;

 if(x==0)
 {
     for(step=1;step<N;step<<=1);
     for(i=0;step;step>>=1)
         if((i+step)<N&&a[i+step]<=val)
             i+=step;
     if(a[i]==val)
     return i;
     return -1;

 }
 else
     if(x==1)
     {
         for(step=1;step<N;step<<=1);
         for(i=0;step;step>>=1)
             if((i+step)<N&&a[i+step]<=val)
             {i+=step;}

             return i;
     }
     else
     {
         for(step=1;step<N;step<<=1);
         for(i=0;step;step>>=1)
             if((i+step)<N&&a[step+i]<val)
             {i+=step;}
         if(a[i]==val)
             return i;
         return i+1;
     }
}
int main()
{
int n,x,m,y;
cin>>n;
for(int i=1;i<=n;i++)
    cin>>a[i];
cin>>m;
for(;m;m--)
{
    cin>>x>>y;
    cout<<cautare(n+1,y,x)<<'\n';

}
}