#include <stdio.h>
#include <vector>

using namespace std;

int N, M;
const int NMAX = 100005;
vector<int> nums(NMAX, 0);


int bsearch0(int x) {
   int l = 0;
   int r = N;
   while (l < r) {
      int m = l + (r - l + 1) / 2;
      if (nums[m] <= x) {
         l = m;
      } else {
         r = m - 1;
      }
   }
   return nums[l] == x ? l+1 : -1;
}

int bsearch1(int x) {
   int l = 0;
   int r = N;
   while (l < r) {
      int m = l + (r - l + 1) / 2;
      if (nums[m] <= x) {
         l = m;
      } else {
         r = m - 1;
      }
   }
   return l+1;
}


int bsearch2(int x) {
   int l = 0;
   int r = N;
   while (l < r) {
      int m = l + (r - l) / 2;
      if (nums[m] >= x) {
         r = m;
      } else {
         l = m + 1;
      }
   }
   return l + 1;
}

int main() {
   freopen("cautbin.in",  "r", stdin);
   freopen("cautbin.out", "w", stdout);
   scanf("%d", &N);
   for (int i = 0; i < N; ++i) {
      scanf("%d", &nums[i]);
   }
   scanf("%d", &M);
   for (int m = 0; m < M; ++m) {
      int q, x;
      scanf("%d %d", &q, &x);
      if (q == 0) {
         printf("%d\n", bsearch0(x));
      } else if (q == 1) {
         printf("%d\n", bsearch1(x));
      } else {
         printf("%d\n", bsearch2(x));

      }
   }
   return 0;
}