#include <stdio.h>   
long v[100005],n;   
long ask0(long x)   
    {   
    long p=0,i,li,ls,mid;   
    li=1;   
    ls=n;   
    mid=(li+ls)/2;   
    while (li<=ls)   
        {   
        if (v[mid]<=x)   
            {   
            if (v[mid]==x) p=1;   
            li=mid+1;   
            mid=(li+ls)/2;   
            }   
        else  
            {   
            ls=mid-1;   
            mid=(li+ls)/2;   
            }   
        }   
    if (p) return mid;   
    else return -1;   
    }   
  
long ask1(long x)   
    {   
    long i,li,ls,mid;   
    li=1;   
    ls=n;   
    mid=(li+ls)/2;   
    while (li<=ls)   
        {   
        if (v[mid]<=x)   
            {   
            i=mid;   
            li=mid+1;   
            mid=(li+ls)/2;   
            }   
        else  
            {   
            ls=mid-1;   
            mid=(li+ls)/2;   
            }   
        }   
    return i;   
    }   
long ask2(long x)   
    {   
    long i,li,ls,mid;   
    li=1;   
    ls=n;   
    mid=(li+ls)/2;   
    while (li<=ls)   
        {   
        if (v[mid]>=x)   
            {   
            i=mid;   
            ls=mid-1;   
            mid=(li+ls)/2;   
            }   
        else  
            {   
            li=mid+1;   
            mid=(li+ls)/2;   
            }   
        }   
    return i;   
    }   
int main()   
{   
long i,m,j;   
int q;   
freopen("cautbin.in","r",stdin);   
freopen("cautbin.out","w",stdout);   
scanf("%ld",&n);   
for (i=1;i<=n;i++)   
    scanf("%ld",&v[i]);   
scanf("%ld",&m);   
for (i=1;i<=m;i++)   
    {   
    scanf("%d %ld",&q,&j);   
    if (!q) printf("%ld\n",ask0(j));   
    else  
    if (q==1) printf("%ld\n",ask1(j));   
    else  
    printf("%ld\n",ask2(j));   
    }   
return 0;   
}