#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[100002],n,m;

int cbin_fixed(int st,int dr,int x)//cea mai mare pozitie pe care se afla un
                                         //element cu valoarea x sau -1
{
     int mid;
     while(st<=dr)
     {
          mid=st+(dr-st)/2;
          if(v[mid]<=x)
               st=mid+1;
          else
               dr=mid-1;
     }
     if(v[dr]==x)
          return dr;
     else
          return -1;
}

int cbin_lower_eq(int st,int dr,int x)// cea mai mare pozitie pe care se afla un
                                               //element cu valoarea mai mica sau egala cu x
{
     int mid;
     while(st<=dr)
     {
          mid=st+(dr-st)/2;
          if(v[mid]<=x)
               st=mid+1;
          else
               dr=mid-1;
     }
    return dr;
}

int cbin_higher_eq(int st,int dr,int x)//cea mai mica pozitie pe care se afla un
                                                  //element cu valoarea mai mare sau egala cu x
{
     int mid;
     while(st<=dr)
     {
          mid=st+(dr-st)/2;

          if(v[mid]>=x)
               dr=mid-1;
          else
               st=mid+1;
     }
    return st;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
          fin>>v[i];
    fin>>m;
    for(int i=1;i<=m;i++)
    {
         int c,x;
         fin>>c>>x;

         if(c==0)
          fout<<cbin_fixed(1,n,x)<<'\n';
         else if(c==1)
          fout<<cbin_lower_eq(1,n,x)<<'\n';
          else
          fout<<cbin_higher_eq(1,n,x)<<'\n';
    }
    return 0;
}