#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N;

vector<int> vec;
vector<int> sol;

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

int  bin1(int low,int high,int x)
{
  if(low > high) return -1;
  int m = (low + high)/2 ;
  if(vec[m] > x)  return bin1(low,m-1,x);
  if(vec[m] < x)  return bin1(m+1,high,x);
  if(vec[m] == x && vec[m+1] == x) return bin1(m+1,high,x);

  return m;
}
int  bin2(int low,int high,int x)
{
  if(low > high) return -1;
  int m = (low + high)/2  ;
  if(vec[m] > x)  return bin2(low,m-1,x);
  if(vec[m] <= x && vec[m+1] <= x) return bin2(m+1,high,x);
  return m;
}
int  bin3(int low,int high,int x)
{
  if(low > high) return -1;
  int m = (low + high)/2 ;
  if(vec[m] < x)  return bin3(m+1,high,x);
  if(vec[m] >= x && vec[m-1] >= x) return bin3(low,m-1,x);

  return m;
}

void solve(int alg,int nr)
{
  if(alg == 0) {
      int a = bin1(0,N,nr);
      cout<< a +1 <<'\n';
    }

    else if(alg == 1)
    {
      int a = bin2(0,N,nr);
      cout<< a + 1 << '\n';
    }
    else if(alg == 2){
      int a = bin3(0,N,nr);
      cout<<a+1 <<'\n' ;
    }
}
int main()
{
  in >> N;
  int nr;
  for(int i = 0; i < N;i++) {
    in >> nr;
    vec.push_back(nr);
  }
  int T,alg,number;
  in >> T;
  for(int i = 0; i < T;i++)
  {
    in >> alg >> number;
    solve(alg,number);
  }
  return 0;
}