#include <iostream>
#include <fstream>
#include <algorithm>
#define Maxx 100001

using namespace std;

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

int N,L,A[Maxx];
int M,x,y,poz,OK,st,dr,mij;
int CB0(int A[],int &N,int y)
{
    int st = 1, dr = N;
    while ( st<=dr )
    {
        int mij = (st+dr)/2;
        if ( A[mij]==y )
        {
            while ( A[mij+1]==A[mij] )
                mij++;
            return mij;
        }
        if ( y < A[mij] )
            dr = mij-1;
        else
            st = mij+1;
    }
    return -1;
}
int CB1(int A[],int &N,int y)
{
    int st = 1, dr = N, mij;
    while ( st<=dr )
    {
        int mij = (st+dr)/2;
        if ( y<A[mij] )
            dr = mij-1;
        else
            st = mij+1;
    }
    int poz = (st+dr)/2;
    if( A[poz] > y)
        poz--;
    return poz;
}
int CB2(int A[],int &N,int y)
{
    int st = 1, dr = N, mij;
    while ( st<=dr )
    {
        int mij = (st+dr)/2;
        if ( y <=A[mij] )
            dr = mij-1;
        else
            st = mij+1;
    }
    int poz = (st+dr)/2;
    if( A[poz] < y)
        poz ++;
    return poz;
}


int main()
{
    f >> N;
    for(int i=1; i<=N; i++)
        f >> A[i];
    f >> M;
    for(int i=1; i<=M; i++)
    {
        f >> x >> y;
        if ( x==0 )
        {
            int poz = CB0(A,N,y);
            g << poz << endl;
        }
        else if ( x==1 )
        {
            int poz = CB1(A,N,y);
            g << poz << endl;
        }
        else
        {
            int poz = CB2(A,N,y);
            g << poz << endl;
        }

    }
    return 0;
}