#include <fstream>

using namespace std;

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

const int N = 1e5+1;
int v[N];

int cbin(int v[],int n,int x,int cer){
    int st=0,dr=n,mij;
    if(cer==0 || cer==1){
        while(st<dr){
        mij=(st+dr)/2;
        if(v[mij]<=x) st=mij+1;
        else dr=mij;
    }
    return st-1;
    }
    else{
        while(st<dr){
        mij=(st+dr)/2;
        if(v[mij]<x) st=mij+1;
        else dr=mij;
        }
        return st;
    }
}

int main()
{
    int n,m,cer,x;
    fin>>n;
    for(int i=1;i<=n;i++) fin>>v[i];
    fin>>m;
    for(int i=0;i<m;i++){
        fin>>cer>>x;
        int ans=cbin(v,n,x,cer);
        if(cer==0 && v[ans]!=x) fout<<-1;
        else fout<<ans<<'\n';
    }
    return 0;
}