#include <fstream>

using namespace std;
 ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int c0(int v[],int n,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 c1(int v[],int n,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 c2(int v[],int n,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()
{
   int n,v[100001],m,c,x;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>c>>x;
        if(c==0) fout<<c0(v,n,x)<<'\n';
        else if(c==1) fout<<c1(v,n,x)<<'\n';
        else if(c==2) fout<<c2(v,n,x)<<'\n';

    }

    return 0;
}