//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 n, int x){
    int first=1, last=n, rez=-1, mid;
    while(first<=last){
        mid=(first+last)/2;
        if(v[mid]==x){
            rez=mid;
            first=mid+1;
        }
        if(v[mid]>x)
            last=mid-1;
        if(v[mid]<x)
            first=mid+1;
    }
    return rez;
}

int op1(int n, int x){
    int first=1, last=n, rez=-1, mid;
    while(first<=last){
        mid=(first+last)/2;
        if(v[mid]==x){
            rez=mid;
            first=mid+1;
        }
        if(v[mid]>x)
            last=mid-1;
        if(v[mid]<x)
            first=mid+1;
    }
    if(rez==-1){
        if(v[mid]<=x)
            return mid;
        else
            return mid-1;

    }
    else
        return rez;
}

int op2(int n, int x){
    int first=1, last=n, rez=-1, mid;
    while(first<=last){
        mid=(first+last)/2;
        if(v[mid]==x){
            rez=mid;
            last=mid-1;
        }
        if(v[mid]>x)
            last=mid-1;
        if(v[mid]<x)
            first=mid+1;
    }
    if(rez==-1){
        if(v[mid]>=x)
            return mid;
        else
            return mid+1;

    }
    else
        return rez;

}
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(n,x)<<'\n';
                break;
                case 1:
                out<<op1(n,x)<<'\n';
                break;
                case 2:
                out<<op2(n,x)<<'\n';
                break;
            }
        }
        return 0;
        in.close();
        out.close();
}