#include <fstream>
#include <iostream>
using namespace std;

int N,M,a[100005];
int request1(int x){
    int l=1, r=N, mid;
    while (l<=r) {

        mid = (l+r) /2;
        if (a[mid]>x) r=mid-1;
        else if (a[mid]<x) l=mid+1;
        else { while (a[mid+1]==x) mid++; return mid;}
    }
    return -1;
}
int request2(int x){
    int l=1, r=N, mid;
    while (l<r) {
    if  (mid == (l+r)/2) r=l;
    else{
    mid = (l+r)/2;
    if (a[mid]>x) r=mid-1;
    else l=mid;
    }
    }
    return l;
}
int request3(int x){
    int l=1, r=N, mid;
    while (l<r){
    if  (mid == (l+r)/2) l=r;
    else{
    mid = (l+r)/2;
    if (a[mid]<x) l=mid+1;
    else r=mid;
    }
    }
    return r;
}
int main(){
    int i,o,x;
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    in >> N;
    for (i=1; i<=N; i++) in >> a[i];
    in >> M;
    for (i=1; i<=M; i++) {
        in >> o >>x;
        if (o==0) out << request1(x) << "\n";
        else if (o==1) out << request2(x) << "\n";
        else out << request3(x) << "\n";

    }
    return 0;
}