#include <cstdio>

using namespace std;

int n,v[1000001],q;

void BinarySearch0(int L,int H,int x)
{
    int sol=-1;
    while(L <= H)
    {
        int M = (L+H)/2;
        if(v[M] < x)
            L = M+1;
        if(v[M] > x)
            H = M-1;
        if(v[M] == x)
        {
            sol = M;
            L = M+1;
        }
    }
    printf("%i\n",sol);
}

void BinarySearch1(int L,int H,int x)
{
    int sol=-1;
    while(L <= H)
    {
        int M = (L+H)/2;
        if(v[M] < x)
            L = M+1;
        if(v[M] > x)
            H = M-1;
        if(v[M] <= x)
        {
            sol = M;
            L = M+1;
        }
    }
    printf("%i\n",sol);
}

void BinarySearch2(int L,int H,int x)
{
    int sol=-1;
    while(L <= H)
    {
        int M = (L+H)/2;
        if(v[M] < x)
            L = M+1;
        if(v[M] > x)
            H = M-1;
        if(v[M] >= x)
        {
            sol = M;
            H = M-1;
        }
    }
    printf("%i\n",sol);
}

void Read()
{
    int tip,x,sol;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%i",&n);
    for(int i=1;i<=n;i++)
        scanf("%i",&v[i]);
    scanf("%i",&q);
    for(int i=0;i<q;i++)
    {
        scanf("%i %i",&tip,&x);
        if(tip == 0)
        {
            BinarySearch0(1,n,x);
        }
        else if(tip == 1)
        {
            BinarySearch1(1,n,x);
        }
        else
        {
            BinarySearch2(1,n,x);
        }
    }
}

int main()
{
    Read();
    return 0;
}