#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, a[100001], m, x, t;

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

int binsearch1 (int n, int x, int a[100001]) {
    int st = 1, dr = n, r = -1;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        
        if(a[mid] <= x) {
            r = mid;
            st = mid + 1;
        }
        else 
            dr = mid - 1;
    }
    return r;
}

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

int main() {
	fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i];
    
    fin >> m;
    for(int i = 1; i <= m; i++) {
        fin >> t >> x;
        if(t == 0)
            fout << binsearch0(n, x, a) << '\n';
        else {
            if(t == 1)
                fout << binsearch1(n, x, a) << '\n';
            else 
                fout << binsearch2(n, x, a) << '\n';
        }
    }
    
    return 0;
}