#include<stdio.h>
long a[100000],n,i,m,f,r,x,pas,p;
/*long cauta(long st,long dr,long x)
{long i,pas;
 for(pas=1;pas<dr;pas<<=1);
 for(i=0;pas;pas>>=1)
    if(i+pas<=dr&&a[i+pas]<=x)i+=pas;
 return i;
} */
int main()
{
 freopen("cautbin.in","r",stdin);
 freopen("cautbin.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;++i)scanf("%ld",&a[i]);
 a[i]=2000000000;
 scanf("%ld",&m);
 for(pas=1;pas<n;pas<<=1);
 for(i=1;i<=m;++i)
    {scanf("%ld%ld",&f,&x);
     if(f<=1)
       {
        for(p=pas,r=0;p;p>>=1)
           if(r+p<=n&&a[r+p]<=x)r+=p;
        if(f==0&&a[r]!=x)r=-1;
        printf("%ld\n",r);
       }
      else
       {
        for(p=pas,r=n;p;p>>=1)
           if(r-p>0&&a[r-p]>=x)r-=p;
        printf("%ld\n",r);
       }
    }
 return 0;
}