#include<fstream>
using namespace std;
long int v[200000],n,m,i,k;
int x;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

long int bin_s(long int x, int q)
{
   long int lo,hi,mid;  
   if(q==0)    
   {
        for(lo=1,hi=n;lo<=hi;)   
        {   
           mid=lo+(hi-lo)/2;   
           if(x<v[mid])hi=mid-1;   
           else if(v[mid]<x)lo=mid+1;   
           else return mid;   
        }   
        return -1;          
   }
   else if(q==1)
        {
           long int temp=0;   
           for(lo=1,hi=n;lo<=hi;)   
           {   
              mid=lo+(hi-lo)/2;   
              if(x>=v[mid])temp=mid, lo=mid+1;   
              else hi= mid-1;   
           }   
           return temp;    
        }
        else
        {
            long int temp=n;
            for(lo=1,hi=n;lo<=hi;)   
            {   
               mid=lo+(hi-lo)/2;   
               if(x<=v[mid])temp=mid, hi=mid-1;   
               else lo= mid+1;   
            }   
            return temp;   
        }
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++) f>>v[i];
    f>>m;
    for(i=1;i<=m;i++) f>>x>>k,g<<bin_s(k,x)<<"\n";
    f.close();
    g.close();
}