#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,i,j,k,a[100101],t,x,r;

int cautbin_0(int r){
    int x;
    x=upper_bound(a+1,a+n+1,r)-a-1;
    if (x>0&&x<=n&&a[x]==r) return x;
    else return 1;

}


int cautbin_1(int r){
    int x=lower_bound(a+1,a+n+1,r+1)-a-1;
    return x;
}

int cautbin_2(int r){
return upper_bound(a+1,a+n+1,r-1)-a;

}


int main()
{
    fin >>n;
    for(i=1;i<=n;i++) fin >>a[i];
    fin>>t;
    for(t;t>0;t--){
        fin >>r>>x;
        if (r==0) fout <<cautbin_0(x);
        if (r==1) fout <<cautbin_1(x);
        if (r==2) fout <<cautbin_2(x);
        fout <<endl;

    }

    return 0;
}