#include <iostream>
#include <cstdio>
#include <algorithm>
#define NMAX 100008

using namespace std;

int n, t;
int a[NMAX];

int binarySearch(int val){
   int i, step;
   for (step = 1; step < n; step <<= 1);
   for (i = 0; step; step >>= 1)
      if (i+step < n && a[i+step] <= val)
         i += step;
   return i;
}

int inverseBinarySearch(int val){
   int i, step;
   for (step = 1; step < n; step <<= 1);
   for (i = n-1; step; step >>= 1)
      if (i-step >= 0 && a[i-step] >= val)
         i -= step;
   return i;
}

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

   scanf("%d\n", &n);
   for (int i = 0; i < n; ++i)
      scanf("%d ", &a[i]);
   scanf("%d\n", &t);
   for (int i = 0; i < t; ++i){
      scanf("%d %d\n", &p, &val);
      if (p == 0 || p == 1){
         poz = binarySearch(val);
         if (p == 0 && a[poz] != val)
            printf("-1");
         else
            printf("%d", poz+1);
      }
      else if (p == 2){
         printf("%d", inverseBinarySearch(val)+1);
      }
      printf("\n");
   }

   return 0;
}