#include <cstdio>

using namespace std;

int n,v[100010];

int cauta_bin1(int x)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(v[mid]<=x) st=mid+1;
        else dr=mid-1;
    }
    if(v[dr]==x) return dr;
    else return -1;
}

int cauta_bin2(int x)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(v[mid]<=x) st=mid+1;
        else dr=mid-1;
    }
    return dr;
}

int cauta_bin3(int x)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(v[mid]<x) st=mid+1;
        else dr=mid-1;
    }
    return st;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int m,a,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&x);
        if(a==0) printf("%d\n",cauta_bin1(x));
        else if(a==1) printf("%d\n",cauta_bin2(x));
        else if(a==2) printf("%d\n",cauta_bin3(x));
    }
    return 0;
}