#include <iostream>

#define NMax 100005

using namespace std;

int Value[NMax], N, M;

int BinarySearch0 (int X)
{
    int S=-1, L=1, R=N;
    while (L<=R)
    {
        int Mid=(L+R)/2;
        if (Value[Mid]==X)
        {
            S=Mid;
            L=Mid+1;
        }
        if (Value[Mid]<X)
        {
            L=Mid+1;
        }
        if (Value[Mid]>X)
        {
            R=Mid-1;
        }
    }
    return S;
}

int BinarySearch1 (int X)
{
    int S=-1, L=1, R=N;
    while (L<=R)
    {
        int Mid=(L+R)/2;
        if (Value[Mid]<=X)
        {
            S=Mid;
            L=Mid+1;
        }
        if (Value[Mid]<X)
        {
            L=Mid+1;
        }
        if (Value[Mid]>X)
        {
            R=Mid-1;
        }
    }
    return S;
}

int BinarySearch2 (int X)
{
    int S=-1, L=1, R=N;
    while (L<=R)
    {
        int Mid=(L+R)/2;
        if (Value[Mid]>=X)
        {
            S=Mid;
            R=Mid-1;
        }
        if (Value[Mid]<X)
        {
            L=Mid+1;
        }
        if (Value[Mid]>X)
        {
            R=Mid-1;
        }
    }
    return S;
}

int main()
{
    freopen ("cautbin.in", "r", stdin);
    freopen ("cautbin.out", "w", stdout);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d", &Value[i]);
    }
    scanf ("%d", &M);
    for (; M>0; --M)
    {
        int Type, X;
        scanf ("%d %d", &Type, &X);
        if (Type==0)
        {
            printf ("%d\n", BinarySearch0 (X));
        }
        if (Type==1)
        {
            printf ("%d\n", BinarySearch1 (X));
        }
        if (Type==2)
        {
            printf ("%d\n", BinarySearch2 (X));
        }
    }
    return 0;
}