#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

const int DIM=1e5+7;
long long v1[DIM];
int n,m;

int bin(long long x,int m)
{
    int l=1;
    int r=m;
    int res=-1;
    while(l<=r)
    {int mid=(l+r)/2;
     if(v1[mid]==x)
        {res=mid;
        l=mid+1;
        }
        else
        if(v1[mid]<x)
        l=mid+1;
        else
        if(v1[mid]>x)
        r=mid-1;
    }
    return res;
}
int bin1(long long x,int m)
{
   int l=1;
   int r=m;
   int res=0;
   while(l<=r)
   {int mid=(l+r)/2;
    if(v1[mid]<=x)
        {l=mid+1;
        res=mid;
        }
    else
        r=mid-1;
   }
   return res;

}
int bin2(long long x,int m)
{
   int l=1;
   int r=m;
   int res=0;
   while(l<=r)
   {int mid=(l+r)/2;
    if(v1[mid]>=x)
        {r=mid-1;
        res=mid;
        }
    else
        l=mid+1;
   }
   return res;

}
int main()
{
    ios::sync_with_stdio(false);

    in >> n ;
    for(int i = 1;i <= n;i++)
        in>> v1[i];
        in >> m;
    for(int i = 1;i <= m;i++)
    {
     long long x,y;
     in >> x >> y;
     if(x==0)
        out << bin(y,n);
     if(x==1)
        out << bin1(y,n);
     if(x==2)
        out << bin2(y,n);
     out<<"\n";
    }
    return 0;
}