#include <iostream>
#include <fstream>
#define MAX 100000

using namespace std;
int caut_bin(int arr[MAX],int cifr,int st, int dr){
    if(st > dr) return -1;
    else{
        int mid = (st + dr)/2;
        if(arr[mid] == cifr && arr[mid + 1] != cifr) return mid + 1;
        else if(arr[mid] < cifr || (arr[mid] == cifr && arr[mid + 1] == cifr)) return caut_bin(arr,cifr,mid + 1, dr);
        else return caut_bin(arr,cifr, st,mid-1);
    }
}

int caut_bin1(int arr[MAX],int cifr,int st, int dr){
    if(st > dr) return -1;
    else{
        int mid = (st + dr)/2;
        if(arr[mid] <= cifr && arr[mid + 1] > cifr) return mid + 1;
        else if(arr[mid] <= cifr && arr[mid + 1] <= cifr) return caut_bin1(arr,cifr, mid + 1,  dr);
        else return caut_bin1(arr,cifr, st, mid -1 );
    }
}

int caut_bin2(int arr[MAX],int cifr,int st, int dr){
    if(st > dr) return -1;
    else{
        int mid = (st + dr)/2;
        if(arr[mid] >= cifr && arr[mid - 1] < cifr) return mid + 1;
        else if(arr[mid] >= cifr && arr[mid - 1] >= cifr) return caut_bin2(arr,cifr, st,mid-1);
        else return caut_bin2(arr,cifr,mid + 1, dr);
    }
}


int main()
{
    ifstream in;
    in.open("cautbin.in");
    ofstream out;
    out.open("cautbin.out");
    int nr,i,arr[MAX];
    in >> nr;
    for (i = 0; i != nr; i++){
        in >> arr[i];
    }
    int oper;
    in >> oper;
    int cifr, tip;
    for (i = 0; i != oper ; i++){
        in >> tip >>cifr;
        int val;
        if(tip == 0)  val = caut_bin(arr,cifr,0,nr);
        else if(tip == 1) {
            if(cifr >= arr[nr-1]) val = nr;
            else val = caut_bin1(arr,cifr,0,nr);
        }
        else if(tip == 2) {
            if(cifr <= arr[0]) val = 1;
            else val = caut_bin2(arr,cifr,0,nr);
        }
        out << val<<endl;
    }
    return 0;
}