#include <cstdio>

using namespace std;
const char InFile[]="cautbin.in";
const char OutFile[]="cautbin.out";
const int DIMN=100010;

int n,m,v[DIMN];

int binarySearch0(int a,int b,int x)
{
    int mid=(a+b)/2;
    if(a>=b)
        return mid;
    else if(x<v[mid])
        return binarySearch0(a,mid-1,x);
    else if(x==v[(a+b)/2])
        return (a+b)/2;
    else return binarySearch0(mid+1,b,x);
}

int binarySearch1(int a,int b,int x)
{
    int mid=(a+b)/2;
    if(a>=b)
        return mid;
    else if(x<=v[mid])
        return binarySearch1(a,mid-1,x);
    else return binarySearch1(mid+1,b,x);
}

int binarySearch2(int a,int b,int x)
{
    int mid=(a+b)/2;
    if(a>=b)
        return mid;
    else if(x<v[mid])
        return binarySearch1(a,mid-1,x);
    else return binarySearch1(mid+1,b,x);
}

int main()
{
    int a,b,t;
    freopen(InFile,"r",stdin);
    freopen(OutFile,"w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&a,&b);
        if(a==0)
        {
            int k=binarySearch0(1,n,b);
            if(b==v[k])
                printf("%d\n",k);
            else printf("-1\n");
        }
        if(a==1)
        {
            printf("%d\n",binarySearch1(1,n,b));
        }
        if(a==2)
        {
            printf("%d\n",binarySearch2(1,n,b));
        }
    }

    return 0;
}