#include <iostream>
#include <vector>

using namespace std;

int v[100001];

int caut(int v[100001], int y, int n){

    int st = 1, dr = n;
    int ans = 1;

    while(st <= dr){
        int med = (st + dr) / 2;

        if(v[med] <= y){
            ans = med;
            st = med + 1;
        }
        else{
            dr = med - 1;
        }
    }

    return ans;

}

int caut2(int v[100001], int y, int n){

    int st = 1, dr = n;
    int ans = 1;

    while(st <= dr){
        int med = (st + dr) / 2;

        if(v[med] >= y){
            ans = med;
            dr = med - 1;
        }
        else{
            st = med + 1;
        }
    }

    return ans;

}

int main(){

    int n, m;
    cin>>n;

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

    cin>>m;
    for(int i = 1; i <= m; i++){
        int q, x;
        cin>>q>>x;

        if(q == 0 || q == 1){
            cout<<caut(v, x, n)<<"\n";
        }
        else{
            cout<<caut2(v, x, n)<<"\n";
        }
    }

    return 0;
}