#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

FILE* in = fopen("cautbin.in", "r");
FILE* out = fopen("cautbin.out", "w");

int a[100000];

int cbin1(int n, int st, int dr){
    if(st>dr){
        return -1;
    }
    int p=st+(dr-st)/2;
    if(a[p]==n&&a[p+1]!=n){
        return p+1;
    }
    else {
        if(a[p]>n){
            return cbin1(n, st, p-1);
        }
        else return cbin1(n, p+1, dr);
    }
}

int cbin2(int n, int st, int dr){
    if(st>dr){
        return dr+1;
    }
    int p=st+(dr-st)/2;
    if(a[p]<=n&&a[p+1]>n){
        return p+1;
    }
    else {
        if(a[p]>n){
            return cbin2(n, st, p-1);
        }
        else return cbin2(n, p+1, dr);
    }
}

int cbin3(int n, int st, int dr){
    if(st>dr){
        return dr+1;
    }
    int p=st+(dr-st)/2;
    if(a[p]>=n&&a[p-1]<n){
        return p+1;
    }
    else {
        if(a[p]>=n){
            return cbin3(n, st, p-1);
        }
        else return cbin3(n, p+1, dr);
    }
}

int main()
{
    int n, i;
    fscanf(in, "%d", &n);
    for(i=0;i<n;i++){
        fscanf(in, "%d", &a[i]);
    }
    int t;
    fscanf(in, "%d", &t);
    for(i=0;i<t;i++){
        int x, y;
        fscanf(in, "%d%d", &x, &y);
        if(x==0){
            fprintf(out, "%d\n",
                    cbin1(y, 0, n-1));
        }
        else if(x==1){
            fprintf(out, "%d\n",
                    cbin2(y, 0, n-1));
        }
        else {
            fprintf(out, "%d\n",
                    cbin3(y, 0, n-1));
        }
    }
    return 0;
}