#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

inline bool cmp(int &x, int &y){
  return x <= y;
}

int n, m, gv[100005];

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

  scanf("%d", &n);
  for(int i = 1; i <= n; ++i)
    scanf("%d", &gv[i]);

  scanf("%d", &m);
  for(int i = 1; i <= m; ++i){
    int op, x;
    scanf("%d%d", &op, &x);

    if(op == 0){
      int left = 1, right = n, mid, last = -1;
      while(left <= right){
        mid = left + (right - left) / 2;
        if(gv[mid] == x){
          last = mid;
          left = mid + 1;
        } else if(gv[mid] < x)
          left = mid + 1;
        else
          right = mid - 1;
      }
      printf("%d\n", last);
    }

    else if(op == 1){
      int left = 1, right = n, mid, last = -1;
      while(left <= right){
        mid = left + (right - left) / 2;
        if(gv[mid] <= x){
          last = mid;
          left = mid + 1;
        }
        else
          right = mid - 1;
      }
      printf("%d\n", last);
    }

    else if(op == 2){
      int left = 1, right = n, mid, last = -1;
      while(left <= right){
        mid = left + (right - left) / 2;
        if(gv[mid] >= x){
          last = mid;
          right = mid - 1;
        }
        else
          left = mid + 1;
      }
      printf("%d\n", last);
    }
  }

  return 0;
}