#include <cstdio>
using namespace std;
int n,st,dr,a[100001],i,m,q,x,k,poz1,poz;
int main()
{freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 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",&q,&x);
     if(q==0){k=0;
              st=1;
              dr=n;
              poz=(st+dr)/2;
              poz1=poz;
              while(k==0)
                   {if((a[poz]==x)&&(a[poz+1]>x)){printf("%d\n",poz);break;}
                      else if(a[poz]>x){dr=poz;poz=(st+dr)/2;if(poz1==poz) poz--;}
                         else if(a[poz]<=x){st=poz;poz=(st+dr)/2;if(poz1==poz) poz++;}
                    if((poz==1)&&(a[poz]!=x)){printf("-1\n");break;}
                    if(poz==1) {printf("1\n");break;}
                    if((poz==n)&&(a[poz]!=x)){printf("-1\n");break;}
                    if(poz==n) {printf("%d\n",n);break;}
                    if((a[poz]>x)&&(a[poz+1]<x)){printf("-1\n");break;}
                   }
             }
     if(q==1){k=0;
              st=1;
              dr=n;
              poz=(st+dr)/2;
              poz1=poz;
              while(k==0)
                   {if((a[poz]<=x)&&(a[poz+1]>x)){printf("%d\n",poz);break;}
                      else if(a[poz]>x){dr=poz;poz=(st+dr)/2;if(poz1==poz) poz--;}
                         else if(a[poz]<=x){st=poz;poz=(st+dr)/2;if(poz1==poz) poz++;}
                    if(poz==1) {printf("1\n");break;}
                    if(poz==n) {printf("%d\n",n);break;}
                   }
             }
     if(q==2){k=0;
              st=1;
              dr=n;
              poz=(st+dr)/2;
              poz1=poz;
              while(k==0)
                   {if((a[poz]>=x)&&(a[poz-1]<x)){printf("%d\n",poz);break;}
                      else if(a[poz]>=x){dr=poz;poz=(st+dr)/2;if(poz1==poz) poz--;}
                         else if(a[poz]<x){st=poz;poz=(st+dr)/2;if(poz1==poz) poz++;}
                    if(poz==1) {printf("1\n");break;}
                    if(poz==n) {printf("%d\n",n);break;}
                   }
             }
    }
}