#include <iostream>
#include <fstream>
#define MAX 100000
using namespace std;

int caut(int cifr, int arr[MAX], int st, int dr){
 if(st > dr)  return -1;
 int m = (dr + st ) / 2;
 if(cifr == arr[m] ){
        int j = 0;
        while(arr[m+j+1] == cifr) j++;
        return m + j+1;
 }
 if(cifr > arr[m]) return caut(cifr,arr,m + 1,dr);
 else return caut (cifr,arr,st,m-1);
}

int caut1(int cifr, int arr[MAX], int st, int dr){
 if(st > dr)  return -1;
 int m = (dr + st ) / 2;
 if(cifr >= arr[m]){
            int j = 0;
            while(cifr >= arr[m+j+1]) j++;
            return m + j+1;
 }
 if(cifr > arr[m]) return caut(cifr,arr,m + 1,dr);
 else return caut (cifr,arr,st,m-1);
}

int caut2(int cifr, int arr[MAX], int st, int dr){
 if(st > dr)  return -1;
 int m = (dr + st ) / 2;
 if(cifr <= arr[m] ){
            int j = 0;
            while(cifr <= arr[m - j-1]) j++;
            return m - j+1;
 }
 if(cifr > arr[m]) return caut(cifr,arr,m + 1,dr);
 else return caut (cifr,arr,st,m-1);
}

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