#include <iostream>
#include <stdio.h>

#define nn 100010

using namespace std;

int s[nn], n, m, op, x;

int caut_zero(int X, int st, int dr)
{
    if( st == dr )
    {
        if(s[st] == X)
            return st;
        if(s[st-1] != X)
            return -1;
        return st-1;
    }
    int mij = (st+dr)/2;
    if( X < s[mij] )
        caut_zero(X, st, mij);
    else
        caut_zero(X, mij+1, dr);
}

int caut_unu(int X, int st, int dr)
{
    if( st == dr )
    {
        if(s[st] > x)
            return st-1;
        return st;
    }
    int mij = (st+dr)/2;
    if( s[mij] <= X )
        caut_unu(X, mij+1, dr);
    else
        caut_unu(X, st, mij);
}

int caut_doi(int X, int st, int dr)
{
    if( st == dr )
        return st;
    int mij = (st+dr)/2;
    if( s[mij] >= X )
        caut_doi(X, st, mij);
    else
        caut_doi(X, mij+1, dr);
}

void read_and_solve()
{
    freopen ("cautbin.in","r",stdin);
    freopen ("cautbin.out","w",stdout);

    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d", &s[i]);

    scanf("%d", &m);
    for(int i=0;i<m;i++)
    {
        scanf("%d %d", &op, &x);

        if(op==0)
            cout << caut_zero(x,1,n) << "\n";
        else if(op==1)
            cout << caut_unu(x,1,n) << "\n";
        else if(op==2)
            cout << caut_doi(x,1,n) << "\n";
    }
}

int main()
{
    read_and_solve();

    return 0;
}