#include <bits/stdc++.h>

using namespace std;

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

int n, m, tip, x, y;
vector <int> v;

int cautbin(int lo, int hi, int x)
{
    int mid=(lo+hi)/2;
    if (lo>=hi)
        return mid;
    if (v[mid]>x)
        return cautbin(lo,mid-1,x);
    else if (v[mid]<=x)
        return cautbin(mid+1,hi,x);
}

void read()
{
    fin >> n;
    for (int i=0;i<n;++i)
    {
        fin >> y;
        v.push_back(y);
    }
    fin >> m;
    for (int i=0;i<m;++i)
    {
        fin >> tip >> x;
        if (tip==0)
            fout << cautbin(0,n-1,x) << "\n";
        else if (tip==1)
            fout << upper_bound(v.begin(),v.end(),x)-v.begin() << "\n";
        else if (tip==2)
            fout << lower_bound(v.begin(),v.end(),x)-v.begin()+1 << "\n";
    }
}


int main()
{
    read();
    return 0;
}