#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 cont = 0, poz;
            for(int j = 0; j < N; j++)
                if(x[i] == a[j]){
                    cont++;
                    poz = j;
                }
            if(cont != 0)
                fout << poz+1 << '\n';
            else fout << "-1" << '\n';
            */
            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 poz;
            for(int j = 0; j < N; j++)
                if(a[j] <= x[i])
                poz = j;
            fout << poz+1 << '\n';
            */
            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 gasit = 0, j = 0, poz;
            while(gasit == 0){
                if(a[j] >= x[i]){
                    gasit = 1;
                    poz = j;
                }
                j++;
            }
            fout << poz+1 << '\n';
            */
            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;
        }
    }
    return 0;
}