#include <iostream>

#include <fstream>

using namespace std;

long binarys( long *a, long q, long x, long start, long finish){
long mid=(start+finish)/2;
if (q==0){
if (start==finish && a[mid]!=x) return -1; else if (start==finish) return mid+1;
if (a[mid]==x && a[mid+1]>x) return mid+1; else if (x>=a[mid]) return binarys(a, 0, x, mid+1, finish); else return binarys(a, 0, x, start, mid-1);
}
if (q==1){
  if (start==finish) return mid;
if (a[mid]<=x && a[mid+1]>x) return mid+1; else if (x>a[mid]) return binarys(a, 1, x, mid+1, finish); else return binarys(a, 1, x, start, mid-1);
}
if (q==2){
if (start==finish) return mid+1;
if (a[mid]>=x && a[mid-1]<x) return mid+1; else if (x>=a[mid]) return binarys(a, 2, x, mid+1, finish); else return binarys(a, 2, x, start, mid-1);
}
}
int main()
{ long n,x;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
fin>>n;
long *t= new long[n+5];
for(long i=0; i<n; i++) fin>>t[i];
fin>>x;
for(long i=0; i<x; i++){
    long a,b;
    fin>>a>>b;
    fout<<binarys( t,a, b, 0 , n-1)<<endl;
}
delete t;
    return 0;
}