#include <iostream>

#include <fstream>

using namespace std;

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