#include <stdio.h>
int nri,x,v[100010];
int cautbin(int in,int sf)
{
    int med,poz=-1;
    while(in<=sf)
    {
        med=(in+sf)/2;
        if(nri==0)
        {
        if(v[med]==x) poz=med;
        if(v[med]<=x) in=med+1;
        else sf=med-1;
        if(v[med]==x) poz=med;
        }
        if(nri==1)
        {
            if(v[med]<=x) {in=med+1;poz=med;}
            else sf=med-1;
        }
        if(nri==2)
        {
            if(v[med]>=x) {sf=med-1;poz=med;}
            else in=med+1;
        }
    }
    return poz;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int i,n,m;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&v[i]);
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&nri,&x);
        printf("%d\n",cautbin(1,n));
    }
}