#include <stdio.h>

using namespace std;
int n, a[100010];

int caut0(int st, int dr, int v)
{
    int m;
    while (st<dr)
    {
        m=(st+dr)/2;
        if (a[m]<=v)
            st=m+1;
        else
            dr=m-1;
    }
    m=(st+dr)/2;
    if (a[m]>v)
        --m;
    if (a[m]==v)
        return m;
    return -1;
}

int caut1(int st, int dr, int v)
{
    int m;
    while (st<dr)
    {
        m=(st+dr)/2;
        if (a[m]<=v)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if (a[m]>v)
        --m;
    return m;
}

int caut2(int st, int dr, int v)
{
    int m;
    while (st<dr)
    {
        m=(st+dr)/2;
        if (a[m]>=v)
            dr=m;
        else
            st=m+1;
    }
    m=(st+dr)/2;
    if (a[m]<v)
        ++m;
    return m;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &n);
    for (int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    int T, m, v;
    for (scanf("%d", &T); T--;)
    {
        scanf("%d %d", &m, &v);
        if (m==0)
            printf("%d\n", caut0(1, n, v));
        else if (m==1)
            printf("%d\n", caut1(1, n, v));
        else if (m==2)
            printf("%d\n", caut2(1, n, v));
    }
    return 0;
}