#include <iostream>
#include <cstdio>
using namespace std;

int v[100001];

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

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

int b2 (int v[100001], int n, int x)
{
    int st,dr,mij;
    st=1;
    dr=n;
    while (st<dr)
    {
        mij=(st+dr)/2;
        if (v[mij]<x)
            st=mij+1;
        else
            dr=mij;
    }
    mij=(st+dr)/2;
    if (v[mij]>=x)
        return mij;
}

int main()
{
    FILE *intrare,*iesire;
    int n,i,x,m,a,st=0,dr=0,mij=0;
    intrare=fopen("cautbin.in","r");
    iesire=fopen("cautbin.out","w");
    fscanf(intrare,"%d",&n);
    for (i=1; i<=n; ++i)
    {
        fscanf(intrare,"%d",&v[i]);
    }
    fscanf(intrare,"%d",&m);
    for (i=1; i<=m; ++i)
    {
        fscanf(intrare,"%d%d",&a,&x);
        if (a==0)
        {
            fprintf(iesire,"%d\n",b0(v,n,x));
        }
        if (a==1)
        {
            fprintf(iesire,"%d\n",b1(v,n,x));
        }
        if (a==2)
        {
            fprintf(iesire,"%d\n",b2(v,n,x));
        }
    }
}