#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
string prob="cautbin";
ifstream in(prob+".in");
ofstream out(prob+".out");
int v[nmax];
int n;
int binS(int tip,int nr){
    int st=1,dr=n;
    if(tip==0||tip==1){
        while(st!=dr){
        int mij=(st+dr+1)/2;
        if(v[mij]<=nr)st=mij;
        else dr=mij-1;
    }
    if(tip==0&&v[st]!=nr)return -1;
    return st;
    }
    while(st!=dr){
        int mij=(st+dr)/2;
        if(v[mij]>=nr)dr=mij;
        else st=mij+1;
    }
    return st;
}
int main(){
    in>>n;
    for(int i=1;i<=n;i++)in>>v[i];
    int m;
    in>>m;
    int tip,x;
    while(m--){
        in>>tip>>x;
        out<<binS(tip,x)<<'\n';
    }
}