#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <vector>
 
#define MAX 1000003
 
using namespace std;
 
ifstream in("cautbin.in");
ofstream out("cautbin.out");
 
int N, M;
int arr[MAX];
 
 
int Search0(int x){
 
    int left = 0, right = N+1;
    while(right - left > 1){
        int mid = (right + left)/2;
        if(x >= arr[mid])
            left = mid;
        else right = mid;
    }
 
    if(x != arr[left])
        return -1;
 
 
    return left;
}
 
int Search1(int x){
 
    int left = 0, right = N+1;
    while(right - left > 1){
        int mid = (right + left)/2;
        if(x >= arr[mid])
            left = mid;
        else right = mid;
    }
 
    return left;
}
 
 
int Search2(int x){
 
    int left = 0, right = N+1;
    while(right - left > 1){
        int mid = (right + left)/2;
        if(x <= arr[mid])
            right = mid;
        else left = mid;
    }
 
    return right;
}
 
 
void binarySearch(){
 
    in >> N;
 
    int op, x, r;
 
    for(int i = 1; i <= N; ++i){
        in >> arr[i];
    }
 
    in >> M;
 
    for(int i = 0; i < M; ++i){
 
        in >> op >> x;
        switch(op){
             
            case(0):
                r = Search0(x);
                out << r << "\n";
                break;
 
            case(1):
                r = Search1(x);
                out << r << "\n";
                break;
 
            case(2):
                r = Search2(x);
                out << r << "\n";
                break;
 
            default:
                out << "Incorrect operation!\n";
        }
    }
}
 
int main(){
 
    binarySearch();
 
    return 0;
}