// CautareBinara.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

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


int n, m, v[100001];

void read()
{
	fscanf(f, "%d", &n);
	for (int i=1; i<=n; i++)
		fscanf(f, "%d", &v[i]);
	fscanf(f, "%d", &m);
}


void binary0(int x)
{
	int lo=1, hi=n, mid;
	while (hi-lo>0)
	{
		mid=lo+(hi-lo)/2;
		if (v[mid]>x) hi=mid-1;
		else lo=mid+1;
	}
	mid=lo+(hi-lo)/2;
	if (v[mid]==x)
		fprintf(g, "%d\n", mid);
	else
		if (v[mid-1]==x)
			fprintf(g, "%d\n", mid-1);
}


void binary1(int x)
{
	int lo=1, hi=n, mid;
	while (hi-lo>0)
	{
		mid=lo+(hi-lo)/2;
		if (v[mid]>x) hi=mid-1;
		else lo=mid+1;
	}
	mid=lo+(hi-lo)/2;
	if (v[mid]<=x)
		fprintf(g, "%d\n", mid);
	else
		if (v[mid-1]<=x)
			fprintf(g, "%d\n", mid-1);
}


void binary2(int x)
{
	int lo=1, hi=n, mid;
	while (hi-lo>0)
	{
		mid=lo+(hi-lo)/2;
		if (v[mid]>=x) hi=mid-1;
		else lo=mid+1;
	}
	mid=lo+(hi-lo)/2;
	if (v[mid]>=x)
		fprintf(g, "%d\n", mid);
	else
		if (v[mid+1]>=x)
			fprintf(g, "%d\n", mid+1);
}



void program()
{
	int o, x;
	for (int i=1; i<=m; i++)
	{
		fscanf(f, "%d%d", &o, &x);
		if (o==1) binary1(x);
		if (o==2) binary2(x);
		if (o==0) binary0(x);
	}
}


int main()
{
	read();
	program();
	return 0;
}