#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
int v[1000001];
int main()
{int n,i,x,t,p,s,m,y;
fin>>n;
for (i=1;i<=n;i++) {fin>>v[i];
                    }
fin>>m;
for (i=1;i<=m;i++) {fin>>x>>y;
                    if (x==0) {t=upper_bound(v+1,v+n+1,y)-v;

                                if (v[y]==v[t]) fout<<t<<endl;
                                else fout<<t-1<<endl;}

                    if (x==1) {p=upper_bound(v+1,v+n+1,y)-v;
                               fout<<p-1<<endl;}
                    if (x==2) {p=lower_bound(v+1,v+n+1,y)-v;
                               fout<<p<<endl;}}


    return 0;
}