#include <fstream>

int le(int x, int y)
{
   return x <= y ? 0 : 1;
}
int ge(int x, int y)
{
   return x >= y ? 0 : -1;
}
int e(int x, int y)
{
   return x == y ? 0 : x < y ? -1 : 1;
}

//int search(int * a, int le, int ri, int key, int (*cond)(int,int), bool first)
//{
//   int res(-1);
//   for(int i = le; i <= ri; ++i)
//   {
//      if(cond(a[i],key) == 0)
//      {
//	 if(res == -1 || (res != -1 && !first)) res = i;
//      }
//   }
//   return res != -1 ? res + 1 : -1; //transform to 1-index
//}

int bsearch(int * a, int le, int ri, int key, int (*cond)(int,int), bool first,bool inv)
{
   int _le(le), _ri(ri), res(-1);
   while(_le <= _ri)
   {
      int m = _le + (_ri - _le) / 2;
      if(cond(a[m],key) == 0)
      {
	 if(res == -1 || (res != -1 && !first))
	    res = m;
	 if(inv) _ri = m - 1;
	 else _le = m + 1;
      }
      else if(cond(a[m],key) == -1)
	 _le = m + 1;
      else
	 _ri = m - 1;
   }
   return res != -1 ? res + 1 : -1; //transform to 1-index
}

int main()
{
   std::ifstream f("cautbin.in");
   std::ofstream g("cautbin.out");

   int N;
   f >> N;
   int* mem=new int[N];
   for(int i=0;i<N;++i) f >> mem[i];

   int tests;
   f >> tests;
   while(tests --)
   {
      int type,key;
      f >> type >> key;
      switch(type)
      {
      case 0:
	 g << bsearch(mem,0,N - 1,key,e,false,false) << '\n';
	 break;
      case 1:
	 g << bsearch(mem,0,N - 1,key,le,false,false) << '\n';
	 break;
      case 2:
	 g << bsearch(mem,0,N - 1,key,ge,false,true) << '\n';
	 break;
      default:
	 break;
      }
   }
   delete[] mem;
   return 0;
}