#include <cstdio>
#include <vector>

using namespace std;

vector <int> v;
int n,m,w;

int cautare0(int st, int dr)
{
    m=st+(dr-st)/2;
    if (v[m]==w)
    {
        printf("%d\n", m+1);
        return 0;
    }
    if (v[m]>w)
        if (m==0 || v[m-1]<w)
            return 1;
        else
            return cautare0(st,m-1);
    else
        if (m==n-1 || v[m+1]>w)
            return 1;
        else
            return cautare0(m+1,dr);
}

void cautare2(int st, int dr)
{
    m=st+(dr-st)/2;
    if (v[m]==w)
    {
        while (m && v[m-1]==v[m])
            --m;
        printf("%d\n", m+1);
    }
    else
    if (v[m]>w)
        if (m==0 || v[m-1]<w)
            printf("%d\n", m+1);
        else
            cautare2(st,m-1);
    else
        cautare2(m+1,dr);
}

void cautare1(int st, int dr)
{
    m=st+(dr-st)/2;
    if (v[m]==w)
        printf("%d\n", m+1);
    else
    if (v[m]>w)
        cautare1(st,m-1);
    else
        if (m==n-1 || v[m+1]>w)
            printf("%d\n",m+1);
        else
            cautare1(m+1,dr);
}

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

    scanf("%d", &n);
    int x,q,t;
    for (int i=0; i<n; i++)
    {
        scanf("%d", &x);
        v.push_back(x);
    }
    for (scanf("%d", &t); t; t--)
    {
        scanf("%d%d", &q, &w);
        if (!q)
        {
            if (cautare0(0,n-1))
                printf("-1\n");
        }
        else if (q==1)
            cautare1(0,n-1);
        else
            cautare2(0,n-1);
    }
    return 0;
}