#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    int N, M, a[100000], cerinta[100000], x[100000];
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin >> N;
    for(int i = 0; i < N; i++)
        fin >> a[i];
    fin >> M;
    for(int i = 0; i < M; i++)
        fin >> cerinta[i] >> x[i];
    for(int i = 0; i < M; i++){
        if(cerinta[i] == 0){

            int st = 0, dr = N, mid, poz = -1;
            while(st <= dr){
                mid = (st + dr) /2;
                if(a[mid] == x[i]){
                    st = mid + 1;
                    poz = mid;
                }
                else if(a[mid] < x[i]){
                    st = mid + 1;
                }
                else{
                    dr = mid - 1;
                }

            }
            if(poz != -1)
            fout << poz+1 << '\n';
            else fout << poz << '\n';
        }
        else if(cerinta[i] == 1){

            int st = 0, dr = N, mid, poz = 0;
            while(st <= dr){
                mid = (st + dr) / 2;
                if(a[mid] == x[i]){
                    st = mid +1;
                    poz = mid;
                }
                else if(a[mid] < x[i]){
                    poz = mid;
                    st = mid +1;
                }
                else{
                    dr = mid - 1;
                }
            }
            fout << poz+1 << '\n';
        }
        else {

            int st = 0, dr = N, mid, poz = 0;
            while(st <= dr){
                mid = (st + dr) / 2;
                if(a[mid] == x[i]){
                    dr = mid - 1;
                    poz = mid;
                }
                else if(a[mid] < x[i]){
                    st = mid + 1;
                }
                else{ /// a[mid] > x[i]
                    dr = mid - 1;
                    poz = mid;
                }
            }
            fout << poz+1 << '\n';
        }
    }
    return 0;
}