#include <iostream>
#include <fstream>

using namespace std;

ifstream in("cautbin.in");
ofstream out("cautbin.out");

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 st+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;
    in>>n;
    for(i=0;i<n;i++){
        in>>a[i];
    }
    int t;
    in>>t;
    for(i=0;i<t;i++){
        int x, y;
        in>>x>>y;
        if(x==0){
            out<<cbin1(y, 0, n-1)<<endl;
        }
        else if(x==1){
            out<<cbin2(y, 0, n-1)<<endl;
        }
        else {
            out<<cbin3(y, 0, n-1)<<endl;
        }
    }
    return 0;
}