#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int a[100002];

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

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

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

int n,i,m,z,q,x;

int main()
{
    fin >> n;
    for (i=1;i<=n;i++) fin >> a[i];
    fin >> m;
    for (i=1;i<=m;i++)
    {
        fin >> q >> x;
        if (q==0) z=q0(n,x);
        if (q==1) z=q1(n,x);
        if (q==2) z=q2(n,x);
        fout << z << "\n";
    }

    return 0;
}