#include <iostream>
#include <fstream>
#define lim 100001

using namespace std;

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

int n,m,rez,v[lim],dr,st,mid,tip,i,x;


int f0(int val)
{
    st=1;
    dr=n;
    int ok=1;

    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(x>=v[mid])
        {
             if(x==v[mid])
                ok=0;
            st=mid+1;
        }

        else
            dr=mid-1;
    }
    if(ok==0)
        return dr;
    dr=-1;
    return dr;
}





int f1(int val)
{
    st=1;
    dr=n;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(x<v[mid])
            dr=mid-1;
        else
            st=mid+1;
    }
    return dr;
}





int f2(int x)
{
    st=1;
    dr=n;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(x<=v[mid])
            dr=mid-1;
        else
            st=mid+1;
    }
    return st;
}




int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];

    fin>>m;
    for(i=1; i<=m; i++)
    {
        fin>>tip>>x;

        ///0
        if(tip==0)
            fout<<f0(x)<<'\n';

        ///1
         if(tip==1)
            fout<<f1(x)<<'\n';

        ///2
        if(tip==2)
            fout<<f2(x)<<'\n';
    }

    fin.close();
    fout.close();
    return 0;
}