#include<bits/stdc++.h>

using namespace std;

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

int a[100100],n,m,x,y;

int binarySearch0(int i, int n, int x){
    int mid;
    while(i <= n){
        mid = i + (n-i)/2;
        if (a[mid]<=x) i = mid + 1;
        else n = mid - 1;
    }
    mid = (i+n) / 2;
    if(a[mid] > x) mid--;
    if(a[mid] == x) return mid;
    return -1;
}

int binarySearch1(int i, int n, int x){
    int mid;
    while(i < n){
        mid = i + (n-i)/2;
        if (a[mid]<=x) i = mid + 1;
        else n = mid;
    }
    mid = (i+n) / 2;
    if(a[mid] > x) --mid;
    return mid;
}

int binarySearch2(int i, int n, int x){
    int mid;
    while(i < n){
        mid = i + (n-i)/2;
        if (a[mid]<x) i = mid + 1;
        else n = mid;
    }
    mid = (i+n) / 2;
    if(a[mid] < x) ++mid;
    return mid;
}

int main(){
    in >> n;
    for (int i=1; i<=n; i++)
        in >> a[i];
    in >> m;
    for (int i=1; i<=m; i++){
        in >> x >> y;
        if (x==0) out << binarySearch0(1,n,y) << "\n";
        else if (x==1) out << binarySearch1(1,n,y) << "\n";
        else out << binarySearch2(1,n,y) << "\n";
    }
    return 0;
}