#include <iostream>
#include <fstream>

using namespace std;

int n,m,x,y;
int sir[1000010];
int rez;

void cautare (int st,int dr)
{
    if(st==dr){
        if(x==0){
            if(!sir[st]==y){
                rez=-1;
                return;
            }else if(sir[st+1]==y)
                cautare(st+1,dr+1);
            else
                rez=st;
        }else if(x==1){
            if(sir[st+1]<=y)
                cautare(st+1,dr+1);
            else
                rez=st;
        }else{
            if(sir[st-1]>=y)
                cautare(st-1,dr-1);
            else
                rez=st;
        }
        return;
    }
    int div=(st+dr)/2;
    if(y<=sir[div]) cautare(st,div);
    else            cautare(div+1,dr);
}

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>sir[i];
    fin>>m;
    for(;m>0;m--){
        fin>>x>>y;
        rez=0;
        cautare(1,n);
        fout<<rez<<'\n';
    }
    return 0;
}