#include <fstream>
#include <iostream>
 
using namespace std;
 
int N, M;
int v[100010];
 
int search(int q, int s, int e, int x) {
    int p = -1;
    while (s <= e) {
        int m = (s + e) / 2;
        if (q <= 1) {
            if (v[m] <= x) {
                p = m;
                s = m + 1;
            }
            else {
                e = m - 1;
            }
        } else {
            if (v[m] >= x) {
                p = m;
                e = m - 1;
            } else {
                s = m + 1;
            }
        }
    }
    if (p == -1)
        return -1;
    if (q <= 1)
        return v[p] == x || q == 1 ? p : -1;
    
    return p;
}
 
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    
    f >> N;
    for (int i = 1; i <= N; i++)
        f >> v[i];
        
    f >> M;
    for (int i = 1; i <= M; i++) {
        int q, x;
        f >> q >> x;
        g << search(q, 1, N, x) << '\n';
    }
    
    f.close();
    g.close();
 
    return 0;
}