#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100010];
inline int cautbin(int x,int n)
{
    int st=0;
    int dr=n;
    int mij=(st+dr)/2;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(v[mij]<x)
            st=mij;
        else
            dr=mij;
    }
    return dr;
}
inline void op0(int x,int n)
{
    int poz=cautbin(x+1,n);
    if(v[poz]!=x)
        poz--;
    if(v[poz]==x)
        out<<poz<<"\n";
    else
        out<<-1<<"\n";
}
inline void op1(int x,int n)
{
    int poz=cauta(x+1);
    if(v[poz] > x)
        poz--;
    out<<poz<<"\n";
}
inline void op2(int x,int n)
{
    int poz=cautbin(x,n);
    out<<poz;
}
int main()
{
    int n;
    in>>n;
    v[0]=-102930;
    for(int i=1;i<=n;i++)
        in>>v[i];
    sort(v+1,v+n+1);
    int T;
    in>>T;
    for(int i=1;i<=T;i++)
    {
        int op;
        in>>op;
        int x;
        in>>x;
        if(op==0)
            op0(x,n);
        if(op==2)
            op2(x,n);
        if(op==1)
            op1(x,n);
    }
    return 0;
}