#include <fstream>
#include <algorithm>
using namespace std;
int v[100001];
int cb0(int st,int dr,int x)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }
    m=(st+dr)/2;
    if(v[m]>x)
        m--;
    if(v[m]==x)
        return m;
    return -1;
}

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

int cb2 (int st, int dr, int x) {
    int m;

    while (st < dr) {
        m = (st + dr) / 2;
        if (v[m] < x)
            st = m + 1;
        else
            dr = m;
    }

    m = (st + dr) / 2;
    if (v[m] < x)
       ++ m;
    return m;
}

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int i, n, m, tip, val;
    f>>n;
    for(i=1; i<=n; ++i)
        f>>v[i];
    f>>m;
    for(i=1; i<=m; ++i)
    {
        f>>tip>>val;
        if(tip==0)
            g<<cb0(1,n,val)<<'\n';
        if(tip==1)
            g<<cb1(1,n,val)<<'\n';
        if(tip==2)
            g<<cb2(1,n,val)<<'\n';
    }
    g.close();
    return 0;
}