#include <fstream>
using namespace std;
const int DMAX = 100001;

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

int CB_0(int n, int sir[], int val)
{
   int st = 1, dr = n, mij, rez = -1;
   while(st <= dr)
   {
      mij = st + (dr-st)/2; // vezi recomandari de implementare

      if(sir[mij] <= val)
      {
         st = mij+1;
         if(sir[mij] == val)
            rez = mij;
      }
      else
         dr = mij-1;
   }
   return rez;
}

int CB_1(int n, int sir[], int val)
{
   int st = 1, dr = n, mij, rez;
   while(st <= dr)
   {
      mij = st + (dr-st)/2;

      if(sir[mij] <= val)
      {
         rez = mij;
         st = mij+1;
      }
      else
         dr = mij-1;
   }
   return rez;
}

int CB_2(int n, int sir[], int val)
{
   int st = 1, dr = n, mij, rez;
   while(st <= dr)
   {
      mij = st + (dr-st)/2;

      if(sir[mij] >= val)
      {
         rez = mij;
         dr = mij-1;
      }
      else
         st = mij+1;
   }
   return rez;
}

int main()
{
   int N, sir[DMAX], M, q, val, i;

   fin >> N;
   for(i = 1; i <= N; i++)
      fin >> sir[i];

   fin >> M;
   for(i = 1; i <= M; i++)
   {
      fin >> q >> val;

      if(q == 0)
         fout << CB_0(N, sir, val) << '\n';
      else if(q == 1)
         fout << CB_1(N, sir, val) << '\n';
      else if(q == 2)
         fout << CB_2(N, sir, val) << '\n';
   }

   fin.close();
   fout.close();
   return 0;
}