#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n, v[100005], m, t, x;
int bin_search0 (int val)
{
    int st=1, dr=n, mij, poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij] == val) {
                st=dr+1;
                poz=mij;
        }
        else{
        if(v[mij] < val) st=mij+1;
        else dr=mij-1;
        }
    }
    if(poz > 0)
        while(v[poz+1] == val)
         poz++;
    return poz;
}

int bin_search1 (int val)
{
    int st=1, dr=n, mij, poz=1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij] <= val) {
                st=mij+1;
                poz=mij;
        }
        else dr=mij-1;
    }
    return poz;
}
int bin_search2 (int val)
{
    int st=1, dr=n, mij, poz=1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij] >= val) {
                dr=mij-1;
                poz=dr;
        }
        else dr=mij-1;
    }
    return poz;
}
int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>v[i];

    in>>m;
    for(int k=1; k<=m; k++)
    {
        in>>t>>x;
        if (t == 0) out<<bin_search0(x)<<'\n';
        if (t == 1) out<<bin_search1(x)<<'\n';
        if (t == 2) out<<bin_search2(x)<<'\n';
    }
    return 0;
}