#include<cstdio>
#define nmax 1000001
using namespace std;

int a[nmax],N,M;

void read();
void solve();
int cautbin(int,int,int,int);

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

    read();
    solve();

    return 0;
}

void read()
{
    int i;
    scanf("%d",&N);
    for (i=1;i<=N;++i)
        scanf("%d",&a[i]);
}

void solve()
{
    int i,c,x;
    scanf("%d",&M);
    for (i=1;i<=M;++i)
    {
        scanf("%d%d",&c,&x);
        printf("%d\n",cautbin(c,1,N,x));
    }
}

int cautbin(int c, int in ,int sf, int val)
{
    int i,mij;
    mij=in+((sf-in)>>1);
    if (sf-in+1>3)
    {
        if (a[mij]==val)
        {
            if (!c||c==1) return cautbin(c,mij,sf,val);
            if (c==2) return cautbin(c,in,mij,val);


        }
        if (a[mij]>val) return cautbin(c,in,mij,val);
        if (a[mij]<val) return cautbin(c,mij,sf,val);

    }
    if (!c)
    {
        for (i=sf;i>=in;--i)
            if (a[i]==val) return i;
        return -1;
    }
    if (c==2)
    {
        for (i=in;i<=sf;++i)
            if (a[i]>=val) return i;
    }
    for (i=sf;i>=in;--i)
            if (a[i]<=val) return i;
}