#include<cstdio>
using namespace std;
int A[100010],N,M,poz;
inline void BS_0(int st,int dr,int x)
{
    if (st>dr) { poz=-1; return; }
    if (st==dr)
        {
            if (A[st]==x) poz=st;
            return;
        }
    int mij=(st+dr)/2;
    if (A[mij]==x) poz=mij;
    if (A[mij]<=x) BS_0(mij+1,dr,x);
            else BS_0(st,mij-1,x);
}
inline int BS_1(int st,int dr,int x)
{
    if (st==dr) return st;
    int mij=(st+dr)/2 + (st+dr)%2;
    if (A[mij]<=x) return BS_1(mij,dr,x);
        else return BS_1(st,mij-1,x);
}
inline int BS_2(int st,int dr,int x)
{
    if (st==dr) return st;
    int mij=(st+dr)/2;
    if (A[mij]<x) return BS_2(mij+1,dr,x);
        else return BS_2(st,mij,x);
}
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]);
    scanf("%d",&M);
    for (int i=1;i<=M;++i)
    {
        int k,x;
        poz=-1;
        scanf("%d%d",&k,&x);
        if (k==0) BS_0(1,N,x);
        if (k==1) poz=BS_1(1,N,x);
        if (k==2) poz=BS_2(1,N,x);
        printf("%d\n",poz);
    }
    fclose(stdin); fclose(stdout);
    return 0;
}