#include<stdio.h>
int n,a[100001],st,dr,mij,m;
void show (int v)
{
     if(v==1)
     printf("-1\n");
     else
     printf("%d\n",mij);
}

int solve (int y,int x,int aux)
{
    st=1;
    dr=n;
    while(st<=dr)
    {
                 mij=(st+dr)/2;
                 if(x==a[mij])
                 {
                              show (2);
                              return 0;
                 }
                 if(x<a[mij])
                 dr=mij-1;
                 else
                 st=mij+1;
    }
    if(y==1 && aux==x)
    solve(y,x-1,aux);
    if(y==2 && aux==x)
    solve(y,x+1,aux);
    if(y==1 && aux!=x)
    show (1);
    if(y==2 && aux!=x)
    show (1);
    if(y==0)
    show (1);
}

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

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