#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N, a[100001], M, type, x;
int bs0(int n)
 {
     int st=1, dr=N, mid;
     while(st<=dr)
        {
            mid=(st+dr)/2;
         if(a[mid]==n) return mid;
         else if(a[mid]>n) dr=mid-1;
         else st=mid+1;
         }
         return -1;
         }
         int bs1(int n)
         {
             int st=1, dr=N, mid;
             while(st<=dr)
                {
                    mid=(st+dr)/2;
                if(a[mid]<=n and (a[mid+1]>n) or mid==N) return mid;
                else if(a[mid]==n) st=mid+1;
                else if(a[mid]>n) dr=mid-1;
                 else st=mid+1;     }
                  return -1; } int bs2(int n) {
                           int st=1, dr=N, mid;
                            while(st<=dr)     {
                                        mid=(st+dr)/2;
         if(a[mid]>=n and a[mid-1]<n) return mid;
         else if(a[mid]==n) dr=mid-1;
          else if(a[mid]>n) dr=mid-1;
          else st=mid+1;     }     return -1;
          } int main() {     f>>N;
          for(int i=1; i<=N; i++) f>>a[i];
          f>>M;     for(int i=1; i<=M; i++)
          {         f>>type>>x;
          if(type==0) g<<bs0(x)<<'\n';
          else if(type==1) g<<bs1(x)<<'\n';
             else g<<bs2(x)<<'\n';     }
              return 0; }