#include <bits/stdc++.h>

using namespace std;
int n, v[100005], t, querry, nr, p1, p2, mid;
int functie_0() {
    p1=1;p2=n;
    while(p1<=p2) {
        mid = p1 + (p2-p1)/2;
        if(v[mid] == nr && (mid == n || v[mid+1] > nr))
            return mid;
        else if(v[mid] <= nr)
            p1=mid+1;
        else if(v[mid] > nr)
            p2=mid-1;
    }
    return -1;
}
int functie_1() {
    p1=1;p2=n;
    while(p1<=p2) {
        mid = p1 + (p2-p1)/2;
        if(v[mid] <= nr && (mid == n || v[mid+1] > nr))
            return mid;
        else if(v[mid] > nr)
            p2 = mid-1;
        else
            p1 = mid+1;
    }
}
int functie_2() {
    p1=1;p2=n;
    while(p1<=p2) {
        mid = p1 + (p2-p1)/2;
        if(v[mid] < nr && (v[mid+1]>=nr || mid==n)) {
            if(mid == n)
                return mid;
            return mid+1;
        }
        else if(v[mid] >= nr)
            p2 = mid-1;
        else if(v[mid] < nr)
            p1 = mid+1;
    }
}
int main () {
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1;i<=n;++i)
        scanf("%d", &v[i]);
    scanf("%d", &t);
    for(int i=1;i<=t;++i) {
        scanf("%d%d", &querry, &nr);
        if(querry == 0)
            printf("%d\n", functie_0());
        else if(querry == 1)
            printf("%d\n", functie_1());
        else if(querry == 2)
            printf("%d\n", functie_2());
    }
    return 0;
}