#include <cstdio>

using namespace std;
int i,j,x,y,s,nr,k,n,m,a[100002];
int bins0(int s,int d,int x)
{
    int m;
    while(s<d)
    {
        m=(s+d)/2;
        if(a[m]>x) d=m-1;
        if(a[m]<=x) s=m+1;

    }
    m=(s+d)/2;
    if(a[m]>x) m--;
    if(a[m]==x) return m;
    return -1;
}
int bins1(int s,int d,int x)
{
    int m;
    while(s<d)
    {
        m=(s+d)/2;
        if(a[m]<=x) s=m+1;
        if(a[m]>x) d=m;

    }
    m=(s+d)/2;
    if(a[m]>x) m--;
    if(a[m]==x) return m;
}
int bins2(int s,int d,int x)
{
    int m;
    while(s<d)
    {
        m=(s+d)/2;
        if(a[m]<x) s=m+1;
        else d=m;

    }
    m=(s+d)/2;
    if(a[m]<x) m++;
    if(a[m]==x) return m;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d\n",&n);
    for(i=1; i<=n; i++)
    scanf("%d ",&a[i]);
    scanf("%d\n",&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d",&x,&y);
        if(x==0) printf("%d\n",bins0(1,n,y));
        if(x==1) printf("%d\n",bins1(1,n,y));
        if(x==2) printf("%d\n",bins2(1,n,y));

    }
    return 0;
}