#include <iostream>
#include <fstream>

using namespace std;

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

const int MAX=1e5+5;
int n,m,v[MAX],st,dr,tip,x;

int CB(int x)
{
    int m;
    st=1;
    dr=n;
    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 CBsup(int x)
{
    int m;
    st=1;
    dr=n;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(v[m]<=x)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if(x<v[m])
        m--;
    return m;
}

int CBinf(int x)
{
    int m;
    st=1;
    dr=n;
    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()
{
    fin >> n;
    for(int i=1;i<=n;i++)
        fin >> v[i];
    fin >> m;
    while(m--)
    {
        fin >> tip >> x;
        if(tip==0)
            fout << CB(x) << '\n';
        if(tip==1)
            fout << CBsup(x) << '\n';
        if(tip==2)
            fout << CBinf(x) << '\n';
    }
    return 0;
}