#include <fstream>
using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int a[100005];

int main(){
  int n;
  f >> n;
  for(int i = 1; i <= n; ++i){
    f >> a[i];
  }

  int m;
  f >> m;
  for(int i = 1; i <= m; ++i){
    int t, x, st = 1, dr = n, rasp, mij;
    f >> t >> x;
    rasp = -1;
    if(t == 0) {
      while(st <= dr){
        mij = (st + dr) / 2;
        if(a[mij] == x){
          rasp = mij;
          st = mij + 1;
        }
        else if(a[mij] < x){
          st =mij + 1;
        }
        else if(a[mij] > x){
          dr = mij - 1;
        }
      }
    } else if(t == 1){
      while(st <= dr){
        mij = (st + dr) / 2;
        if(a[mij] <= x){
          rasp = mij;
          st = mij + 1;
        }
        else if(a[mij] > x){
          dr = mij- 1;
        }
      }
    } else if(t == 2){
      while(st <= dr){
        mij = (st + dr) / 2;
        if(a[mij] >= x){
          rasp = mij;
          dr = mij - 1;
        }
        else if(a[mij] < x){
          st = mij + 1;
        }
      }
    }
    g << rasp << endl;
    }

  return 0;
}