#include <iostream>
#include <fstream>
#include <algorithm>

#define nmax 100005
using namespace std;

int n,m;
int a[nmax];

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

int task_1(int st,int dr,int x)
{
    if(st==dr)
        if(a[st]==x)
            return st;
        else return -1;
    int mij=(st+dr)/2;
    if(a[mij]>=x && a[mij+1]!=a[mij])
        return task_1(st,mij,x);
    else
        return task_1(mij+1,dr,x);
}

int task_2(int st,int dr,int x)
{
    if(st==dr)
        if(a[st]<=x)
            return st;
        else return -1;
    int mij=st+(dr-st)/2;
    if(a[mij]<=x && a[mij+1]!=a[mij])
        return task_2(st,mij,x);
    else
        return task_2(mij+1,dr,x);
}

int task_3(int st,int dr,int x)
{
    if(st==dr)
        if(a[st]>=x)
            return st;
        else return nmax;
    int mij=st+(dr-st)/2;
    if(a[mij]>=x)
        return task_3(st,mij,x);
    else
        return task_3(mij+1,dr,x);
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    read();
    int tip,x;
    for(int i=1;i<=m;i++,printf("\n"))
        {
            scanf("%d %d",&tip,&x);

            if(tip==0)
                printf("%d",task_1(1,n,x));
            if(tip==1)
                printf("%d",task_2(1,n,x));
            if(tip==2)
                printf("%d",task_3(1,n,x));
        }
    return 0;
}