#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m[100002],dr,st,x,a,b,mij;
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>m[i];
    fin>>x;
    for(int i=1;i<=x;i++){
        fin>>a>>b;
        int poz=0;
        st=1,dr=n;
        while(st<=dr){
            mij=(st+dr)/2;
            if(m[mij]==b){
                poz=mij;
                break;
            }
            if(m[mij]>b)
                dr=mij-1;
            else
                st=mij+1;
            poz=mij;
        }
        if(a==0){
            if(m[poz]==b){
                while(m[poz+1]==b)
                    poz++;
                fout<<poz<<'\n';
            }
            else
                fout<<-1<<'\n';
        }
        else if(a==1){
            while(m[poz+1]==b)
                poz++;
            if(m[poz]>b)
                fout<<poz-1<<'\n';
            else
                fout<<poz<<'\n';
        }
        else{
            while(m[poz-1]==b)
                poz--;
            if(m[poz]<b)
                fout<<poz+1<<'\n';
            else
                fout<<poz<<'\n';
        }
        //cout<<poz;
    }
    return 0;
}