#include <iostream>

using namespace std;

const int NMAX = 100000;
int N;

int vec[NMAX];

int bin1(int l, int r, int v) {
   int m;
   while (l <= r) {
      m = l + (r - l) / 2;
      if (vec[m] <= v) {
         l = m + 1;
      } else {
         r = m - 1;
      }
   }

   m = l + (r - l) / 2;
   if (vec[m] > v) {
      m--;
   }
   if (vec[m] == v) {
      return m;
   }
   return -1;
}

int bin2(int l, int r, int v) {
   int m;
   while (l < r) {
      m = l + (r - l) / 2;
      if (vec[m] <= v) {
         l = m + 1;
      } else {
         r = m;
      }
   }

   m = l + (r - l) / 2;
   if (vec[m] > v) {
      m--;
   }
   return m;
}


int bin3(int l, int r, int v) {
   int m;
   while (l < r) {
       m = l + (r - l) / 2;
      if (vec[m] < v) {
         l = m + 1;
      } else {
         r = m;
      }
   }

   m = l + (r - l) / 2;
   if (vec[m] < v) {
      ++m;
   }
   return m;
}


int main() {
   freopen("cautbin.in", "r", stdin);
   freopen("cautbin.out", "w", stdout);

   scanf("%d", &N);

   for (int i = 1 ; i <= N; ++i) {
      scanf("%d", &vec[i]);
   }

   int M;
   scanf("%d", &M);

   for (int  i = 0; i < M; ++i) {
      int op, val;
      scanf("%d %d", &op, &val);
      if (op == 0) {
         printf("%d\n", bin1(1, N, val));
      } else if (op == 1) {
         printf("%d\n", bin2(1, N, val));
      } else {
         printf("%d\n", bin3(1, N, val));
      }
   }
   return 0;
}