#include <iostream>
#include <fstream>
#define INF 1999999999

using namespace std;

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

int n, v[100005];
int m, tip, target;
int st, md, dr;

int main (){
    fin>>n; v[0]=INF; v[n+1]=INF;
    for(int i=1; i<=n; i++)
        fin>>v[i];


    fin>>m;
    for(int i=1; i<=m; i++){
        fin>>tip>>target;
        if(tip == 0){
            st=1;
            dr=n;
            while(st <= dr){
                md=(st+dr)/2;
                if(v[md] <= target)
                    st=md+1;
                else
                    dr=md-1;
            }

            if(v[st-1] == target)
                fout<<st-1<<"\n";
            else
                fout<<-1<<"\n";
        }else if(tip == 1){
            st=1;
            dr=n;
            while(st <= dr){
                md=(st+dr)/2;
                if(v[md] <= target)
                    st=md+1;
                else
                    dr=md-1;
            }

            if(v[st-1] <= target)
                fout<<st-1<<"\n";
            else
                fout<<-1<<"\n";
        }else{
            st=1;
            dr=n;
            while(st <= dr){
                md=(st+dr)/2;
                if(v[md] < target)
                    st=md+1;
                else
                    dr=md-1;
            }

            if(v[st] >= target && 1 <= st && st <= n)
                fout<<st<<"\n";
            else
                fout<<-1<<"\n";
        }
    }

    return 0;
}