#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int cautBin(int v[], int n, int x, int st, int dr, int tip) {
   
    while (st <= dr) {
    int mid = (st + dr) / 2;
    if (v[mid] < x) {
        st =  mid + 1;
        if (tip == 1)
        if(mid < n && v[mid] <= x && v[mid + 1] > x)
            return mid;
        else if (mid == n && v[mid] <= x)
            return mid;
    }
       
    else if (v[mid] > x) {
        dr = mid - 1;
        if (tip == 2)
        if (mid > 1 && v[mid] >= x && v[mid - 1] < x)
            return mid;
        else if (mid == 1 && v[mid] >= x)
            return mid;
    }
    else if (v[mid] == x) {
        if (tip == 0 || tip == 1) {
            while (v[mid] == x) {
                mid ++;
            }
            return (mid - 1);
        }
        if (tip == 2) {
            while (v[mid] == x) {
                mid --;
            }
            return (mid + 1);
        }
       
    }
    }
    
    return -1;
}


int main() {
    int m, n, v[100000], tip, x;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    fin >> m;
    for (int i = 1; i <= m; i++) {
        fin >> tip >> x;
        fout<< cautBin(v, n, x, 1, n, tip) << endl;
        }
}