#include <fstream>
#define Nmax 10000


using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int  A[Nmax];
int bisort0(int inc, int sf,int k)
{
    int mid;
    while(inc<=sf)
    {
        mid=(inc+sf)/2;
        if(A[mid]<=k)
        {
            inc=mid+1;
        }else{sf=mid-1;}

    }
    mid=(inc+sf)/2;
    if(A[mid] > k)mid--;
    if(A[mid]==k)return mid;
    return -1;



}
int bisort1(int inc, int sf, int k)
{
     int mid;
    while(inc<sf)
    {
        mid=(inc+sf)/2;
        if(A[mid]<=k)
        {
            inc=mid+1;
        }else{sf=mid;}

    }
    mid=(inc+sf)/2;
    if(A[mid]>k)mid--;
    return mid;

}
int bisort2(int inc, int sf,int k)
{
     int mid;
    while(inc<sf)
    {
        mid=(inc+sf)/2;
        if(A[mid]<k)
        {
            inc=mid+1;
        }else{sf=mid;}

    }
    mid=(inc+sf)/2;
    if(A[mid]<k)mid++;
     return mid;

}

int main()
{
    int i,k,caz,N,M;
    in>>N;
    for(i=1;i<=N;i++)
        {in>>A[i];}
    in>>M;
    while(M!=0)
    {
        M--;
        in>>caz>>k;
        if(caz==0)out<<bisort0(1, N, k)<<"\n";
        if(caz==1)out<<bisort1(1, N, k)<<"\n";
        if(caz==2)out<<bisort2(1, N, k)<<"\n";

    }
    return 0;
}