#include <fstream>
#include <cmath>
#define LIM 1000001
using namespace std;

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

int n;
int v[LIM];
int m;
int a,b;

int cerinta0(int nr){
    int poz = 0;

    for(int p = (1<<30); p > 0; p /= 2){
        if(poz + p <= n && v[poz + p] <= nr){
            poz += p;
            
        }
    }

    if(v[poz] != nr){
        return -1;
    }
    return poz;
}

int cerinta1(int nr){
    int poz = 0;

    for(int p = (1<<30); p > 0; p /= 2){
        if(poz + p <= n && v[poz + p] <= nr){
            poz += p;
            
        }
    }
    
    
    return poz;
}

int cerinta2(int nr){
    int poz = 0;
    
    for(int p = 1; p < (1<<30); p *= 2){
        if(poz + p <= n && v[poz + p] < nr){
            poz += p;
            
        }
    }
    poz++;
    if(v[poz] != nr){
        return -1;
    }
    
    return poz;
}

int main(){
    fin >> n;
    for(int i=1; i<=n; ++i){
        fin >> v[i];
    }
    fin >> m;
    for(int i=0; i<m; ++i){
        fin >> a >> b;
        /// a - cerinta | b - nr cautat
        if(a == 0){
            fout << cerinta0(b) << "\n";
        }else if(a == 1){
            fout << cerinta1(b) << "\n";
        }else{
            fout << cerinta2(b) << "\n";
        }
    }


    return 0;
}