#include <bits/stdc++.h>
using namespace std;

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

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

int main(void) {
	int n, v[100000], m, x, y; 
	
	fin >> n;
    for (int i = 0; i < n; i++)
        fin >> v[i];
    
    fin >> m;    
    while(m--) {
        fin >> x >> y;
        fout << cautBin(x, y, n, v) << endl;
    }
    
	return 0;
}