#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,v[100005];
int m,t,val;
int binsearch0(int p,int u, int val)
{
    int mijl;
    while(p<=u)
    {
        mijl=(p+u)/2;
        if(v[mijl]<=val) p=mijl+1;
        else u=mijl-1;
    }
    mijl=(p+u)/2;
    if(v[mijl]>val) mijl--;
    if(v[mijl]==val) return mijl;
    return -1;
}
int binsearch1(int p,int u, int val)
{
    int mijl;
    while(p<u)
    {
        mijl=(p+u)/2;
        if(v[mijl]<=val) p=mijl+1;
        else u=mijl;
    }
    mijl=(p+u)/2;
    if(v[mijl]>val) mijl--;
    return mijl;
}
int binsearch2(int p,int u, int val)
{
    int mijl;
    while(p<u)
    {
        mijl=(p+u)/2;
        if(v[mijl]<val) p=mijl+1;
        else u=mijl;
    }
    mijl=(p+u)/2;
    if(v[mijl]<val) mijl++;
    return mijl;
}

int main()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++) fin>>v[i];
    fin>>m;
    while(m--)
    {
        fin>>t>>val;
        if(t==0) fout<<binsearch0(1,n,val)<<"\n";
        else if(t==1) fout<<binsearch1(1,n,val)<<"\n";
            else if(t==2) fout<<binsearch2(1,n,val)<<"\n";
    }
}