#include <stdio.h>


const int NMAX = 100010;
int N;

int vec[NMAX];

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 logN;

   for (logN = 1;  logN <= N; logN <<= 1);

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

   for (int  j = 0; j < M; ++j) {
      int op, val;
      scanf("%d %d", &op, &val);
      int i, lg;
      if (op < 2) {
         for (i = 0, lg=logN; lg; lg >>= 1) {
            if (i + lg <= N && vec[i+lg] <= val) {
               i += lg;
            }
         }

         if (op == 0) {
            if (vec[i] != val) {
               printf("-1\n");
            } else {
               printf("%d\n", i);
            }
         } else {
            printf("%d\n", i);
         }
      } else {
          for (i = N, lg=logN; lg; lg >>= 1) {
            if (i - lg >= 0 && vec[i-lg] >= val) {
               i -= lg;
            }
         }
         printf("%d\n",i);
      }
   }
   return 0;
}