#include <fstream>

using namespace std;

const int MAX = 100001;

int V[MAX];

int bin0(int,int,int);
int bin1(int,int,int);
int bin2(int,int,int);

int main(){
   ifstream fin("cautbin.in");
   ofstream fout("cautbin.out");

   int N , M;

   fin >> N;
   for (int i = 1; i <= N; ++i)
       fin >> V[i];

   fin >> M;

   int type , value;

   while (M--){
    fin >> type >> value;
    if (type == 0) fout << bin0(1,N,value);
    if (type == 1) fout << bin1(1,N,value);
    if (type == 2) fout << bin2(1,N,value);
    }

   fin.close();
   fout.close();
   return 0;
}

int bin0(int left,int right,int value){
   int middle;

   while (left <= right){
    middle = (left + right) / 2;
    if (V[middle] <= value) left = middle + 1;
    else right = middle - 1;
    }
   middle = (left + right) / 2;
   if (V[middle] > value) --middle;
   if (V[middle] == value) return middle;
   return -1;
}

int bin1(int left,int right,int value){
   int middle;

   while (left < right){
    middle = (left + right) / 2;
    if (V[middle] <= value) left = middle + 1;
    else right = middle - 1;
    }
   middle = (left + right) / 2;
   if (V[middle] > value) --middle;
   return middle;
}

int bin2(int left,int right,int value){
   int middle;

   while (left < right){
    middle = (left + right) / 2;
    if (V[middle] < value) left = middle + 1;
    else right = middle - 1;
    }
   middle = (left + right) / 2;
   if (V[middle] < value) ++middle;
   return middle;
}