#include<cstdio>
long long a[100001],x,n,m,i,c,st,dr,mid;
int main()
{
    FILE *fin, *fout;
    fin=fopen("cautbin.in", "r");
    fout=fopen("cautbin.out", "w");
    fscanf(fin, "%lld",&n);

    for(i=1; i<=n; i++)
        scanf("%lld",&a[i]);

    fscanf(fin, "%lld",&m);
    for(; m; m--)
    {
        fscanf(fin, "%lld%lld",&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)
                fprintf(fout, "%lld\n",st);
            else
                fprintf(fout, "-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;
            }
            fprintf(fout,"%lld\n",st);
        }
        else
        {
            st=0;
            dr=n;
            while(dr-st-1)
            {
                mid=(st+dr)/2;
                if(a[mid]>=x)dr=mid;
                else st=mid;
            }
            fprintf(fout,"%lld\n",dr);
        }
    }
    return 0;
}