#include <cstdio>

const char iname[] = "cautabin.in";
const char oname[] = "cautabin.out";
const int MAXN = 100005;

int n, m, a[MAXN];
int (*fp[3])(int);

int cautaBin0(int val){
    int lo = 0, hi = n-1;
    int ans = -1;
    while(lo <= hi){
        int mid = lo + ((hi - lo) >> 1);
        if(a[mid] == val) ans = mid+1;
        if(a[mid] <= val)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return ans;
}

int cautaBin1(int val){
    int lo = 0, hi = n-1;
    while(lo < hi){
        int mid = lo + ((hi - lo + 1) >> 1);
        if(a[mid] > val)
            hi = mid -1;
        else
            lo = mid;
    }
    return lo+1;
}

int cautaBin2(int val){
    int lo = 0, hi = n-1;
    while(lo < hi){
        int mid = lo + ((hi - lo) >> 1);
        if(a[mid]>=val)
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo+1;
}

void read(){
    freopen(iname, "r", stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", a+i);
}
void solve(){
    scanf("%d", &m);
    for(int i = 0; i < m; ++i){
        int c, x;
        scanf("%d %d", &c, &x);
        printf("%d\n", fp[c](x));
    }
}
int main()
{
    freopen(iname, "r", stdin);
    freopen(oname, "w", stdout);
    fp[0] = cautaBin0;
    fp[1] = cautaBin1;
    fp[2] = cautaBin2;
    read();
    solve();
    return 0;
}