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

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

    while (r-l>1) {
        int mid=(l+r)/2;
        if (a[mid]>x)
            r=mid-1;
        else if (a[mid]<x)
            l=mid+1;
        else
            l=mid;
    }
    if (a[l+1]==x)
        l++;

    if (l==0)
        return -1;

    return l;
}
int request2(int x){
    int l=1, r=N, mid;

    while (r-l>1){
        mid=(l+r)/2;
        if (a[mid]>x)
            r=mid-1;
        else
            l=mid;
    }
    if (a[l+1]<=x)
        l++;

    return l;
}
int request3(int x){
    int l=1, r=N, mid;

    while (l<r){
        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;
}