#include <bits/stdc++.h>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

int cautbin2(int x, int n, int a[]){
    int st = 0, dr = n - 1;
    int mid = 0;
    int sol=n+1;
    while (st<=dr)
    {
        mid=(st+dr)/2;
        if (a[mid]>=x)
        {
            sol=mid;
            dr=mid-1;
        }
        else
            st=mid+1;
    }
    return sol + 1;
}

int cautbin1(int x, int n, int a[]){
    int st = 0, dr = n - 1;
    int ok = 0;
    int mid = 0;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(x >= a[mid]){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
    return st;
}

int cautbin0(int x, int n, int a[]){
    int st = 0, dr = n - 1;
    int ok = 0;
    int mid = 0;
    int cer1 = 0;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(x == a[mid]){
            ok = 1;
            cer1 = mid;
        }
        if(x >= a[mid]){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
    if(ok == 1){
        return cer1;
    }
    return -1;
}

int main() {
    int n, a[100001];
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    int m;
    cin >> m;
    for(int i = 0;i < m;i++){
        int c, x;
        cin >> c >> x;
        if(c == 0){
            cout << cautbin0(x, n, a) + 1 << '\n';
        }
        else if(c == 1){
            cout << cautbin1(x, n, a) << '\n';
        }
        else{
            cout << cautbin2(x, n, a) << '\n';
        }
    }
    return 0;
}