#include <fstream>
#define Nmax 100010
using namespace std;
ifstream in;
ofstream out;

int N, A[Nmax],i,M,op,b;
long op0(int st, int dr) {
    int mij;
    while (st!=dr) {
        mij=(st+dr+1)/2;
        if (b>=A[mij])
           st=mij; else
           dr=mij-1;
    }
    if (b==A[st]) return st+1;
    return -1;
}
long op1(int st, int dr) {
    int mij;
    while (st!=dr) {
        mij=(st+dr+1)/2;
        if (b>=A[mij])
           st=mij; else
           dr=mij-1;
    }
    if (b<A[st]) return st;
    return st+1;
}
long op2(int st, int dr) {
    int mij;
    while (st!=dr) {
        mij=(st+dr)/2;
         if(A[mij]>=b)
             dr=mij;
          else st=mij+1;
          }
     if(A[st]<A[mij])
         return st+2;
     return st+1;
}
int main() {
    in.open("cautbin.in");
    out.open("cautbin.out");
    in >> N;
    for (i=0;i<N;i++)
    {
        in >> A[i];
    }
    in >> M;
    for (i=0;i<M;i++) {
        in >> op >> b;
        switch (op) {
            case 0:out << op0(1,N) << "\n";
            break;
            case 1:out << op1(1,N) << "\n";
            break;
            case 2:out << op2(1,N) << "\n";
            break;
        }
    }
    return 0;
}