#include <cstdio>
using namespace std;

int n,logn,m,a[100002];

int cautbin1(int x)
{
    int i,step;
    for(step=logn,i=1;step;step>>=1)
    {
        i+=step;
        if(i>n) i-=step;
        else if(a[i]>x) i-=step;
    }
    if(a[i]==x) return i;
    return -1;
}

int cautbin2(int x)
{
    int i,step;
    for(step=logn,i=1;step;step>>=1)
    {
        i+=step;
        if(i>n) i-=step;
        else if(a[i]>x) i-=step;
    }
    return i;
}

int cautbin3(int x)
{
    int i,step;
    for(step=logn,i=n;step;step>>=1)
    {
        i-=step;
        if(i<1) i+=step;
        else if(a[i]<x) i+=step;
    }
    return i;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int i,t,x;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(logn=1;logn<n;logn<<=1);
    while(m)
    {
        --m;
        scanf("%d%d",&t,&x);
        switch(t)
        {
            case 0: printf("%d\n",cautbin1(x)); break;
            case 1: printf("%d\n",cautbin2(x)); break;
            case 2: printf("%d\n",cautbin3(x)); break;
        }
    }
    return 0;
}