//Se da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul:
//0 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 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
//2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
#include <iostream>
#include <fstream>
using namespace std;
int v[100001], n, m;
int op0(int first, int last, int x){
    int mid;
    mid = (first+last)/2;
    while(first<=last){
        if(v[mid]<=x)
            first=mid+1;
        else
            last=mid-1;
        mid = (first+last)/2;
    }
    if(v[mid]==x)
        return mid;
    return -1;                      //daca pe pozitia aflata mid nu se afla x inseamna ca nu e in sir
}
int op1(int first, int last, int x){
    int mid = (first+last)/2;
    while(first<=last){
        if(v[mid]<=x)
            first=mid+1;
        else
            last=mid-1;
        mid = (first+last)/2;
    }
        return mid;        //daca x nu e in sir last=mid o sa ajunga valoarea < cea mai apropiata
}

int op2(int first, int last, int x){
    int mid = (first+last)/2;;
     while(first<last){
        if(v[mid]<x)           //< strict pentru a lua cea mai mica pozitie daca x se repeta
            first=mid+1;
        else
            last=mid-1;
        mid = (first+last)/2;
     }
        return mid+1;         //daca x nu e in sir mid+1 va fi valoarea > cea mai apropiata

}
int main(){
    fstream in("cautbin.in");
    ofstream out("cautbin.out");
        int op,x,i;
        in>>n;
        for(i=1; i<=n; i++)
            in>>v[i];
        in>>m;
        for(i=1;i<=m;i++){
            in>>op>>x;
            switch(op){
                case 0:
                out<<op0(1,n,x)<<'\n';
                break;
                case 1:
                out<<op1(1,n,x)<<'\n';
                break;
                case 2:
                out<<op2(1,n,x)<<'\n';
                break;
            }
        }
        return 0;
}