#include <stdio.h>
#include <stdlib.h>
int v[100002];
int main()
{
    int x,a,b,i,n;
    long long s,m,d;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d",&v[i]);
    scanf("%d",&x);
    v[0]=2147483647;
    for(i=0; i<x; i++){
        scanf("%d%d",&a,&b);
        s=1;
        d=n;
        if(a==0 || a==1)
        {
            while(s<=d)
            {
                m=(s+d)/2;
                if(v[m]<=b) s=m+1;
                else d=m-1;
            }
            if(a==0){
                if(v[d]==b) printf("%d\n",d);
                else printf("-1\n");
            }
            else
                printf("%d\n",d);
        }
        else{
            while(s<=d)
            {
                m=(s+d)/2;
                if(v[m]<b) s=m+1;
                else d=m-1;
            }
            printf("%d\n",s);
        }
    }

    return 0;
}