#include <cstdio>
#define Nmax 100002
using namespace std;
int n , a[Nmax];
int m;
int funct0(int x);
int funct1(int x);
int funct2(int x);


int main()
{
    freopen("cautbin.in" , "r" , stdin);
    freopen("cautbin.out" , "w" , stdout);
    scanf("%d ", &n);
    for(int i = 0 ; i < n ; ++i)
        scanf("%d" , &a[i]);
    scanf("%d",&m);
    while(m)
    {
        int no , x;
        scanf("%d %d" , &no , &x);
        switch (no)
        {
            case 0:
            {
                printf("%d\n",funct0(x));
                break;
            }
            case 1:
            {
                printf("%d\n",funct1(x));
                break;
            }
            case 2:{ //funct2(x);
                printf("%d\n",funct2(x));
                break;
                }
        }
        m--;
    }

    return 0;
}
int funct0(int x)
{
    int st = 0 ; int dr = n ;
    int mij ;
    while ( st < dr )
    {
        mij = (st + dr) / 2;
        if(x > a[mij])
            st = mij+1;
        if(x < a[mij])
            dr = mij;
        else
        {
            while(a[mij-1] == x)
                mij++;
            return mij-1;
        }
    }
    return -1;
}
int funct1(int x)
{
    int st = 0,dr = n;
    int mij ;
    while ( st < dr )
    {
        mij = (st+dr)/2;
        if(x >= a[mij])
            st = mij+1;
        else
            dr = mij;
    }
    mij = (st + dr)/2;
    if(a[mij-1] > x)
        mij--;
    return mij;
}
int funct2(int x)
{
    int st = 0,dr = n;
    int mij ;
    while ( st < dr )
    {
        mij = (st+dr)/2;
        if(x > a[mij])
            st = mij+1;
        else
            dr = mij;
    }
    mij = (st+dr)/2;
    if(a[mij-1]<x)
        mij++;
    return mij;

}