#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int a[100005];

int main(){
  int n;
  fin >> n;
  for(int i=1;i<=n;++i){
    fin >> a[i];
  }
  int m;
  fin >> m;
  for(int i=1;i<=m;++i){
    int op, x, st=1, dr=n, rasp, mij;
    fin >> op >> x;
    rasp=-1;
    if(op == 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(op == 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(op == 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;
        }
      }
    }
    fout << rasp << '\n';
  }
  
  return 0;
}