#include <iostream>
#include <cstdio>
#define Dmax 100100
using namespace std;

int v[Dmax]; int N,M;

int CAUTARE(int y, int &m)
{
    int i,j,GASIT=0;
    i=1; j=N;
    while(i<=j && GASIT==0)
    {
        m=(i+j)/2;
        if(y==v[m]) {GASIT=1;}
        else
            if(y>v[m]) i=m+1;
                else j=m-1;
    }
    return GASIT;
}

int CAUTARE_2(int y)
{
    int i,j,GASIT=0,m;
    i=1; j=N;
    while(i<=j && GASIT==0)
    {
        m=(i+j)/2;
        if(y>v[m]) {GASIT=1;}
        else
            if(y>v[m]) i=m+1;
                else j=m-1;
    }
    return m;
}

int CAUTARE_3(int y)
{
    int i,j,GASIT=0,m;
    i=1; j=N;
    while(i<=j && GASIT==0)
    {
        m=(i+j)/2;
        if(y<v[m]) {GASIT=1;}
        else
            if(y>v[m]) i=m+1;
                else j=m-1;
    }
    return m;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int i,j,k,x,m;

    scanf("%d",&N);
    for(i=1; i<=N; i++) scanf("%d",&v[i]);

    scanf("%d",&M);
    for(i=1; i<=M; i++)
    {
        scanf("%d%d", &k, &x);
        switch(k)
        {
            case 0:
                {
                    if(CAUTARE(x,m)==1) {
                                            while(v[m]==v[m+1] && m<N) m=m+1;
                                            printf("%d",m);
                                        }
                                        else printf("-1");
                }break;
            case 1:
                {
                    if(CAUTARE(x,m)==1) {
                                            while(v[m]==v[m+1] && m<N) m=m+1;
                                            printf("%d",m);
                                        }
                                        else
                                        {
                                            m=CAUTARE_2(x);
                                            while(v[m]<x && m<=N) m++;
                                            printf("%d",m-1);
                                        }
                }break;
            case 2:
                {
                    if(CAUTARE(x,m)==1) {
                                            while(v[m]==v[m-1] && m>1) m=m-1;
                                            printf("%d",m);
                                        }
                                        else
                                        {
                                            m=CAUTARE_3(x);
                                            while(v[m]>x && m>=1) m--;
                                            printf("%d",m+1);
                                        }
                }break;
        }
        printf("\n");
    }

    return 0;
}