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

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

int n,m;
int V[100005];
int bs(int x,int t){
    int st=1;
    int dr=n;
    int mij=(st+dr)/2;
    while(st<dr){
        if(x>V[mij]){
            st=mij+1;
        }
        else if(x<=V[mij]){
            dr=mij;
        }
        mij=(st+dr)/2;
    }
    if(t==2){
        if(V[mij]==x){
            while(V[mij]==x)
                mij--;
            return mij+1;
        }
        else{
            while(V[mij-1]==V[mij])
                mij--;
            return mij;
        }
    }
    else if(t==1){
        if(V[mij]==x){
            while(V[mij]==x)
                mij++;
            return mij-1;
        }
        else{
            while(V[mij]==V[mij-1])
                mij++;
            return mij-1;
        }
    }
    else if(t==0){
        if(V[mij]==x){
            while(V[mij]==x)
                mij++;
            return mij-1;
        }
        return -1;
    }
}
int main(){
    int t,x;
    in>>n;
    for(int i=1;i<=n;i++){
        in>>V[i];
    }
    in>>m;
    for(int i=1;i<=m;i++){
        in>>t>>x;
        out<<bs(x,t)<<"\n";
    }
    return 0;
}