#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

const int MAX_N = 100005;
int n;
int v[MAX_N];

const int MAX_Q = 100005;
int qcnt;
struct query{
    int tip;
    int val;
}q;

int st, md, dr, sol;

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

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

    fin>>qcnt;
    while(qcnt--){
        fin>>q.tip>>q.val;

        if(q.tip == 0){ /// 0
            st = 1;
            dr = n;
            sol = -1;
            while(st <= dr){
                md = ((dr - st)>>1) + st;
                if(v[md] <= q.val){
                    sol = md;
                    st = md + 1;
                }else
                    dr = md - 1;
            }
            if(v[sol] != q.val)
                sol = -1;

        }else if(q.tip == 1){ /// 1
            st = 1;
            dr = n;
            sol = 1;
            while(st <= dr){
                md = ((dr - st)>>1) + st;
                if(v[md] <= q.val){
                    sol = md;
                    st = md + 1;
                }else
                    dr = md - 1;
            }

        }else{ /// 2
            st = 1;
            dr = n;
            sol = n;
            while(st <= dr){
                md = ((dr - st)>>1) + st;
                if(v[md] >= q.val){
                    sol = md;
                    dr = md - 1;
                }else
                    st = md + 1;
            }
        }

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

    return 0;
}