#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
 int n,q,a[100005];
int Cbin0(int x)
{ int i,mid,st=1,dr=n;
   while(st<=dr)
   { mid=(st+dr)/2;
      if (a[mid]<=x) st=mid+1;
       else dr=mid-1;
   }
   mid=(st+dr)/2;
   if (mid>n || x<a[mid]) mid--;

   if (a[mid]==x) return mid;
    else return -1;
}

int Cbin1(int x)
{ int i,mid,st=1,dr=n;
   while(st<=dr)
   { mid=(st+dr)/2;
      if (a[mid]<=x) st=mid+1;
       else dr=mid-1;
   }
   mid=(st+dr)/2;
   if (a[mid]>x) mid--;
    return mid;
}


int Cbin2(int x)
{ int i,mid,st=1,dr=n;
   while(st<=dr)
   { mid=(st+dr)/2;
      if (a[mid]>=x) dr=mid-1;
       else st=mid+1;
   }
   mid=(st+dr)/2;
   if (a[mid]<x) mid++;
    return mid;

}

int main()
{ int i,t,x;
    f>>n;
    for(i=1;i<=n;i++)
     f>>a[i];

     f>>q;
     for(i=1;i<=q;i++)
     { f>>t>>x;
       if (t==0) g<<Cbin0(x)<<"\n";
       if (t==1) g<<Cbin1(x)<<"\n";
       if (t==2) g<<Cbin2(x)<<"\n";
     }
    return 0;
}