#include <stdio.h>
#include <stdlib.h>
#define N 100001

int n,v[N];
int BS(int x)
{ int i,j,m;
  i=1; j=N;
  while (i<=j) {
    m=i+(j-i)/2;
    if (v[m]==x) return m;
     else if (v[m]<x) i=m+1;
       else j=m-1;
  }
  return -1;
}
int BS1(int x)
{ int i,j,m,poz=0;
  i=1; j=N;
  while (i<=j) {
    m=i+(j-i)/2;
    if (v[m]<=x) {
	poz=m; i=m+1;
      }
     else i=m-1;
  }
  return poz;
}
int BS2(int x)
{ int i,j,m,poz=0;
  i=1; j=N;
  while (i<=j) {
    m=i+(j-i)/2;
    if (v[m]>=x) {
	poz=m; i=m-1;
      }
     else i=m+1;
  }
  return poz;
}

int main()
{
    int i,m,x,tip;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
	scanf("%d",&v[i]);
    scanf("%d",&m);
    while (m--){
	  scanf("%d %d",&tip,&x);
	  if (tip==0) printf("%d\n",BS(x));
	    else if (tip==1) printf("%d\n",BS1(x));
	      else printf("%d\n",BS2(x));
	}
    return 0;
}