#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, i, x, a, v[100000];
int sbin0(int k){
    if(k/2 == 0 || k < 0 || k > n){
        return -1;
    }else{
        if(v[k] < x){
            sbin(k + k/2);
        }else{
            if(v[k] > x){
                sbin(k - k/2);
            }else if(v[k] == x){
                    if(v[k+1] == x){
                        sbin(k+1);
                    }else{
                        return k;
                    }
                }
        }
    }
}
int sbin1(int k){
    if(v[k] < x){
        sbin(k + k/2);
    }else{
        if(v[k] > x){
            sbin(k - k/2);
        }else if(v[k] == x){
                if(v[k+1] == x){
                    sbin(k+1);
                }else{
                    return k;
                }
            }
    }
}
int sbin2(int k){
    if(v[k] < x){
        sbin(k + k/2);
    }else{
        if(v[k] > x){
            sbin(k - k/2);
        }else if(v[k] == x){
                if(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;
        if(a == 0)  fout << sbin0(n/2) << endl;
        if(a == 1)  fout << sbin1(n/2) << endl;
        if(a == 2)  fout << sbin2(n/2) << endl;
    }

    return 0;
}