#include <iostream>
#define NMAX 100001
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n, v[NMAX], m;

void read(){
    in>>n;
    for(int i=1; i<=n; i++)in>>v[i];
    in>>m;
}

int binSearch0(int l, int r, int a){
    int m, bestPos=-1;
    while(l<=r){
        m=l+(r-l)/2;
        if(v[m]==a){
            bestPos=m;
            l=m+1;
        }else if(a<v[m]){
            r=m-1;
        }else{
            l=m+1;
        }
    }
    return bestPos;
}

int binSearch1(int l, int r, int a){
    int m, bestPos;
    while(l<=r){
        m=l+(r-l)/2;
        if(v[m]<=a){
            bestPos=m;
            l=m+1;
        }else if(a<v[m]){
            r=m-1;
        }else{
            l=m+1;
        }
    }
    return bestPos;
}

int binSearch2(int l, int r, int a){
    int m, bestPos;
    while(l<=r){
        m=l+(r-l)/2;
        if(v[m]>=a){
            bestPos=m;
            r=m-1;
        }else if(a<v[m]){
            r=m-1;
        }else{
            l=m+1;
        }
    }
    return bestPos;
}

int main(){
    read();
    int x, num;
    for(int i=1; i<=m; i++){
        in>>num>>x;
        if(num==0){
            out<<binSearch0(1, n, x)<<"\n";
        }else if(num==1){
            out<<binSearch1(1, n, x)<<"\n";
        }else{
            out<<binSearch2(1, n, x)<<"\n";
        }
    }
    return 0;
}