#include <fstream>

using namespace std;

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

#define nmax 100010

int v[nmax];

int b0(int inc,int sf,int val){
    int m;
    while(inc<=sf){
        m=(inc+sf)/2;
        if(v[m]<=val)
            inc=m+1;
        else
            sf=m-1;}
    m=(inc+sf)/2;
    if(v[m]>val)
        m--;
    if(v[m]==val)
        return m;
    return -1;}

int b1(int inc,int sf,int val){
    int m;
    while(inc<sf){
        m=(inc+sf)/2;
        if(v[m]<=val)
            inc=m+1;
        else
            sf=m;}
    m=(inc+sf)/2;
    if(v[m]>val)
        return --m;}

int b2(int inc,int sf,int val){
    int m;
    while(inc<sf){
        m=(inc+sf)/2;
        if(v[m]<=val)
            inc=m+1;
        else
            sf=m;}
    m=(inc+sf)/2;
    if(v[m]>val)
        return ++m;}
int n;

int main()
{
    fin>>n;
    int i,val,m,tip;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>tip>>val;
        if(tip==0)
            fout<<b0(1,n,val);
        if(tip==1)
            fout<<b1(1,n,val);
        if(tip==2)
            fout<<b2(1,n,val);
    }

    return 0;
}