#include <iostream>

FILE * fin= fopen("cautbin.in","r");
FILE * fout= fopen("cautbin.out","w");

int n,m;
int v[100050];

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

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

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

int main()
{
  fscanf(fin,"%d",&n);
  for(int i=1;i<=n;i++)
    fscanf(fin,"%d",&v[i]);
  fscanf(fin,"%d",&m);
  for(int i=0;i<m;i++)
  {
    int c, x;
    fscanf(fin,"%d %d",&c,&x);
    if(c==0)
      fprintf(fout,"%d\n",normBS(x,1,n));
    else if(c==1)
      fprintf(fout,"%d\n",lowBS(x,1,n));
    else
      fprintf(fout,"%d\n",highBS(x,1,n));
  }
}