#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, i, x, a, v[100000];

//0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
//1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
//2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
int sbin(int k){
    if(a == 0 && k/2 == 0 || k < 0 || k > n ) return -1;
    if(v[k] < x) sbin(k + k/2);
    else if(v[k] > x) sbin(k - k/2);
    else if(v[k] == x)
            if(a != 2 && v[k+1] == x)sbin(k+1);
            else if(a == 2 && v[k-1] == x)sbin(k-1);
            else return k;
}

int main(){
    int m;
    fin >> n;
    for(i = 1; i <= n; i++){
        fin >> v[i];
    }
    fin >> m;
    for(i = 0; i < m; i++){
        fin >> a >> x;
        fout << sbin(n/2) << endl;
    }

    return 0;
}