#include <iostream>
#include <fstream>
#define MAX 100002
using namespace std;
int n,v[MAX],m,t,x;

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

int cb0(int x){
    /// cea mai mare pozitie pe care se afla un element cu valoarea x
    /// sau -1 daca aceasta valoare nu se gaseste in sir
    /// 1 1 1 1 1 1 0 0 0 0
    ///           ^
    /// 1 - v[i] <= x, 0 - altfel
    int st = 1, dr = n;
    int ans = 0;
    while(st <= dr){
        int mid = (st+dr)/2;
        if(v[mid] <= x){
            /// ne aflam pe 1, vrem sa mergem pe 0 (in dreapta)
            st = mid+1;
            ans = mid;
        }else{
            /// ne aflam pe 0, vrem sa mergem pe 0 (in stanga)
            dr = mid-1;
        }
    }
    return (v[ans]==x?ans:-1);
}

int cb1(int x){
    /// cea mai mare pozitie pe care se afla un element cu
    /// valoarea mai mica sau egala cu x in sir
    /// (acelasi cod ca la cb0 doar fara ultima verificare la final)
    int st = 1, dr = n;
    int ans = 0;
    while(st <= dr){
        int mid = (st+dr)/2;
        if(v[mid] <= x){
            st = mid+1;
            ans = mid;
        }else{
            dr = mid-1;
        }
    }
    return ans;
}

int cb2(int x){
    /// cea mai mica pozitie pe care se afla un element cu
    /// valoarea mai mare sau egala cu x in sir
    /// 0 0 0 0 1 1 1 1
    ///         ^
    /// 0 - v[i] < x, 1 - v[i] >= x
    int st = 1, dr = n;
    int ans = 0;
    while(st <= dr){
        int mid = (st+dr)/2;
        if(v[mid] >= x){
            dr = mid-1;
            ans = mid;
        }else{
            st = mid+1;
        }
    }
    return ans;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> v[i];
    }
    fin >> m;
    for(int i = 1; i <= m; i++){
        fin >> t >> x;
        if(t == 0){
            fout << cb0(x) << "\n";
        }else if(t == 1){
            fout << cb1(x) << "\n";
        }else{
            fout << cb2(x) << "\n";
        }
    }
    return 0;
}