#include <stdio.h>
FILE *f,*g;

int N, M, v[100005];

int C1(int x)
{
	 int lo, hi, mid;

	 for (lo = 1, hi = N; lo <= hi; )
	 {
		  mid = lo + (hi-lo) / 2;
		  if (x < v[mid]) hi = mid-1;
		  else if (v[mid] < x) lo = mid+1;
		  else return mid;
	 }
	 return -1;
}

int C2(int x)
{
	 int lo, hi, mid, last = 0;

	 for (lo = 1, hi = N; lo <= hi; )
	 {
		  mid = lo + (hi-lo) / 2;
		  if (v[mid] <= x) last = mid, lo = mid+1;
		  else hi = mid-1;
	 }
	 return last;
}

int C3(int x)
{
	 int lo, hi, mid, last = N+1;

	 for (lo = 1, hi = N; lo <= hi; )
	 {
		  mid = lo + (hi-lo) / 2;
		  if (x <= v[mid]) last = mid, hi = mid-1;
		  else lo = mid+1;
	 }
	 return last;
}

int main()
{
	 int i, t, x;

	f=fopen("cautbin.in","r");
	g=fopen("cautbin.out","w");


	 fscanf(f,"%d", &N);
	 for (i = 1; i <= N; ++i)
		  fscanf(f,"%d", &v[i]);

	 fscanf(f,"%d", &M);
	 for (i=1;i<=M;i++)
	 {
		  fscanf(f,"%d %d", &t, &x);
		  if (!t)
				fprintf(g,"%d\n", C1(x));
		  else if (t == 1)
				fprintf(g,"%d\n", C2(x));
		  else
				fprintf(g,"%d\n", C3(x));
	 }
	 return 0;
	 }