#include <cstdio>

using namespace std;
int a[100005],n,m,q,type,x;
int cautarebinarareg1(int st,int dr,int y)
{

    int mid=0;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(y>=a[mid])
            st=mid+1;
        else
            dr=mid-1;
    }
    mid=(st+dr)/2;
    if(a[mid]>y)
        mid--;
    if(a[mid]==y)
        return mid;
    return -1;
}
int cautarebinarareg2(int st,int dr,int y)
{
    int mid=0;
    while(st<dr)
    {
        mid=(dr+st)/2;
        if(y>=a[mid])
            st=mid+1;
        else
            dr=mid;
    }
    mid=(dr+st)/2;
    if(a[mid]>y)
        mid--;
        return mid;
}
int cautarebinarareg3(int st,int dr,int y)
{
    int mid=0;
    while(st<dr)
    {
        mid=st+(dr-st)/2;
        if(y>a[mid])
            st=mid+1;
        else
            dr=mid;
    }
    mid=st+(dr-st)/2;
    if(a[mid]<x)
        mid++;
    return mid;
}
void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        scanf("%d %d",&type,&x);
        if(type==0)
            printf("%d\n",cautarebinarareg1(1,n,x));
        else if(type==1)
            printf("%d\n",cautarebinarareg2(1,n,x));
        else
            printf("%d\n",cautarebinarareg3(1,n,x));
    }
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    citire();
    return 0;
}