#include <cstdio>
#define N 1000100
using namespace std;

int v[N];

inline int cautbin0(int st,int dr,int x)
{
    int mij;
    while( st <= dr )
    {
        mij = (st+dr)/2;
        if( v[mij] <= x )
            st = mij+1;
        else
            dr = mij -1;
    }
    mij = (st+dr)/2;
    if(v[mij] > x)--mij;
    if(v[mij] == x )
        return mij;
    return -1;
}

inline int cautbin1(int st,int dr,int x)
{
    int mij;
    while( st <= dr )
    {
        mij = (st+dr)/2;
        if( v[mij] <= x )
            st = mij+1;
        else
            dr = mij -1;
    }
    mij = (st+dr)/2;
    return mij;
}
inline int cautbin2(int st, int dr,int x)
{
    int mij;
    while( st <= dr )
    {
        mij = (st+dr)/2;
        if( v[mij] < x )
            st = mij+1;
        else
            dr = mij -1;
    }
    mij = (st+dr)/2;
    if(v[mij] < x)
        ++mij;
    return mij;
}
inline void Solve()
{
    int n,m,i,tip,val;
    FILE *f = fopen("cautbin.in","r");
    FILE *g = fopen("cautbin.out","w");
    fscanf(f,"%d ",&n);
    for(i = 1; i <= n; ++i)
        fscanf(f,"%d ",&v[i]);

    fscanf(f,"%d ",&m );

    while( m-- )
    {
        fscanf(f,"%d %d", &tip, &val);
        if( tip == 0 )
            fprintf(g,"%d \n",cautbin0(1,n,val));
        if( tip == 1 )
            fprintf(g,"%d \n",cautbin1(1,n,val));
        if( tip == 2 )
            fprintf(g,"%d \n",cautbin2(1,n,val));

    }

    fclose(f);
    fclose(g);
}
int main()
{
    Solve();
    return 0;
}