#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-st)>>1);
        if (a[m]<=v)
            st=m+1;
        else
            dr=m-1;
    }
    m=st+((dr-st)>>1);
    if (a[m]>v && a[m-1]==v)
        return m-1;
    return -1;
}

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

int caut2(int st, int dr, int v)
{
    int m;
    while (st<dr)
    {
        m=st+((dr-st)>>1);
        if (a[m]<=v)
            dr=m-1;
        else
            st=m;
    }
    m=st+((dr-st)>>1);
    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; 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;
}