#include<stdio.h>
long a[100001],x,n,m,i,c,st,dr,mid;
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]);
    scanf("%ld",&m);
    for(; m; m--)
    {
        scanf("%ld%ld",&c,&x);
        if(c==0)
        {
            st=1;
            dr=n+1;
            while(dr-st-1)
            {
                mid=(st+dr)/2;
                if(a[mid]<=x)st=mid;
                else dr=mid;
            }
            if(a[st]==x)printf("%ld\n",st);
            else printf("-1\n");
        }
        else if(c==1)
        {
            st=1;
            dr=n+1;
            while(dr-st-1)
            {
                mid=(st+dr)/2;
                if(a[mid]<=x)st=mid;
                else dr=mid;
            }
            printf("%ld\n",st);
        }
        else
        {
            st=0;
            dr=n;
            while(dr-st-1)
            {
                mid=(st+dr)/2;
                if(a[mid]>=x)dr=mid;
                else st=mid;
            }
            printf("%ld\n",dr);
        }
    }
    return 0;
}