#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001],st,dr,x;
int n,m,poz,i,tip;
int cautbin1(int st,int dr,int x)
{
    int poz=-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(x==v[mid])
        {
            poz=mid;
            st=mid+1;
        }
        else
        {


            if(x<v[mid])

            dr=mid-1;
            else
                st=mid+1;
        }

    }
    return poz;
}
int cautbin2(int st,int dr,int x)
{
   int poz=0;
   while(st<=dr)
   {
       int mid=(st+dr)/2;
       if(v[mid]<=x)
       {
        poz=mid;
       st=mid+1;
       }
       else
        dr=mid-1;
   }
   return poz;
}
int cautbin3(int st,int dr,int x)
{

int poz=0;
   while(st<=dr)
   {
       int mid=(st+dr)/2;
       if(v[mid]>=x)
       {
        poz=mid;
       dr=mid-1;
       }
       else
        st=mid+1;
   }
   return poz;
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
    in>>v[i];
in>>m;
for(int i=1;i<=m;i++){
    in>>tip>>x;
    if(tip==0){
        out<<cautbin1(1,n,x);
        out<<'\n';
    }
        else
    if(tip==1){
                out<<cautbin2(1,n,x);
        out<<'\n';
    }
    else
    {
                out<<cautbin3(1,n,x);
        out<<'\n';
    }

}
    return 0;
}