#include <bits/stdc++.h>
#define NMAX 100001

using namespace std;

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

int i , a[NMAX] , n , m , tip , numar , poz;

int cautare(int x){
  int mij = 0 , st = 1 , dr = n , poz = -1;
  while(st <= dr)
  {
      mij = (dr - st)/ 2 + st;
      if(a[mij] == x) poz = mij , st = mij + 1;
      else if(a[mij] < x)st = mij + 1;
      else dr = mij - 1;
  }
  return poz;
}

int cautare_2(int x){
  int mij = 0 , st = 1 , dr = n , poz = -1;
  while(st <= dr)
  {
      mij = (dr - st)/ 2 + st;
      if(a[mij] <= x) poz = mij , st = mij + 1;
      else dr = mij - 1;
  }
  return poz;
}

int cautare_3(int x){
  int mij = 0 , st = 1 , dr = n , poz = -1;
  while(st <= dr)
  {
      mij = (dr - st)/ 2 + st;
      if(a[mij] >= x) poz = mij , dr = mij - 1;
      else if(a[mij] < x)st = mij + 1;
  }
  return poz;
}

int main()
{
   fin>>n;
   for(i=1;i<=n;i++)f>>a[i];
   fin>>m;
   for(i=1;i<=m;i++)
   {
       fin>>tip>>numar;
       if(tip == 0)
       {
           poz = cautare(numar);
           fout<<poz<<'\n';
       }
       else if(tip == 1)
      {
          poz  = cautare_2(numar);
          fout<<poz<<'\n';
      }
      else {
         poz = cautare_3(numar);
         fout<<poz<<'\n';
      }
   }
    return 0;
}