#include <cstdio>
using namespace std;

int cautareBinara(int* vect, int n, int key, int type);

int main(void)
{
  int m, n, i, qType, qKey;
  int *vect;

  freopen("cautbin.in","r",stdin);
  freopen("cautbin.out","w",stdout);

  scanf("%d",&n);
  vect = new int[n];
  for (i=0;i<n;i++)
  {
    scanf("%d",&vect[i]);
  }

  scanf("%d",&m);
  for (int i=0;i<m;i++)
  {
    scanf("%d %d",&qType,&qKey);
    printf("%d\n",cautareBinara(vect,n,qKey,qType));
  }

  delete[] vect;
  return 0;
}

int cautareBinara(int* vect, int n, int key, int type)
{
  int power = 1;
  while (power < n) power <<= 1;
  power >>= 1;

  if (type != 2)
  {
    int i = 0;
    while (i<n && power > 0)
    {
      if (vect[i+power] <= key)
      {
        i = i+power;
      }
      power >>= 1;
    }

    if (type == 0 && vect[i] != key) return -1;
    else return i+1;
  }
  else
  {
    int i = n-1;
    while (i>=0 && power > 0)
    {
      if (vect[i-power] >= key)
      {
        i -= power;
      }
      power >>= 1;
    }
    return i+1;
  }

}