#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

int n,m;
vector<int> V;

int bs(int x,int t){
    auto it=V.begin();
    if(t==0){
        it=upper_bound(V.begin(),V.end(),x);
        it--;
        if(*it!=x)
            return -1;
    }
    else if(t==1)
        it=upper_bound(V.begin(),V.end(),x),
        it--;
    else
        it=lower_bound(V.begin(),V.end(),x);
   return it-V.begin()+1;
}
void read(){
    in>>n;
    for(int i=1,x;i<=n;i++){
        in>>x;
        V.push_back(x);
    }
    in>>m;
}
void queries(){
    for(int i=1,t,x;i<=m;i++){
        in>>t>>x;
        out<<bs(x,t)<<"\n";
    }
}
int main(){
    read();
    queries();
    return 0;
}