#include <cstdio>
#define MAX_N 100001

int N, M, V[MAX_N];

void read(void);
void solve(void);
int BS_0(int);
int BS_1(int);
int BS_2(int);

int main()
{
    freopen("cautbin.in","rt",stdin);
    freopen("cautbin.out","wt",stdout);
    read();
    for(int t = 0; t<M; ++t)
        solve();
}

void read()
{
    scanf("%d\n",&N);
    for(int i = 0; i<N; ++i)
        scanf("%d",V + i);
    scanf("%d",&M);
}

void solve()
{
    int k, x;
    scanf("%d %d",&k,&x);
    if(k == 0)
        printf("%d\n",BS_0(x));
    if(k == 1)
        printf("%d\n",BS_1(x));
    if(k == 2)
        printf("%d\n",BS_2(x));
}

int BS_0(int k)
{
    int li = 0, lf = N;
    while(li <= lf)
    {
        int m = li + ((lf - li) >> 1);
        if(V[m] == k)
            return m + 1;
        if(V[m] < k)
            li = m + 1;
        else
            lf = m - 1;
    }
    return -1;
}

int BS_1(int k)
{
    int li = 0, lf = N;
    while(li <= lf)
    {
        int m = li + ((lf - li) >> 1);
        if(V[m] <= k && ((V[m + 1] > k) || (m + 1 == N)))
            return m + 1;
        if(V[m] > k)
            lf = m - 1;
        else
            li = m + 1;
    }
}

int BS_2(int k)
{
    int li = 0, lf = N;
    while(li <= lf)
    {
        int m = li + ((lf - li) >> 1);
        if(V[m] >= k && ((V[m - 1] < k) || (m == 0)))
            return m + 1;
        if(V[m] > k)
            lf = m - 1;
        else
            li = m + 1;
    }
}