#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
int v[DIM];
int n,t,tip,x,i;
int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    fin>>t;
    for (;t--;){
        fin>>tip>>x;
        if (tip == 0){

            int st = 1, dr = n, sol = 0;
            while (st <= dr){
                int mid = (st + dr)>>1;
                if (v[mid] <= x){
                    sol = mid;
                    st = mid+1;
                } else dr = mid-1;
            }

            if (v[sol] != x || sol == 0)
                fout<<-1<<"\n";
            else fout<<sol<<"\n";

            continue;
        }
        if (tip == 1){ /// valoare mai mica sau egala cu x
            int st = 1, dr = n, sol = 0;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (v[mid] <= x){
                    st = mid+1;
                    sol = mid;
                } else dr = mid-1;
            }
            fout<<sol<<"\n";
            continue;
        }
        /// tip 2
        int st = 1, dr = n, sol = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (v[mid] >= x){
                sol = mid;
                dr = mid-1;
            } else st = mid+1;
        }

        fout<<sol<<"\n";
    }



    return 0;
}