#include<iostream>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <iomanip>
#include <string>
using namespace std;
#define DIMMAX 100000000
int n, m;
//long long int *cerinte, *sir;
int poz, sir[DIMMAX], cerinte[DIMMAX];
void caut0(int st, int dr, int x, int &poz)
{
	int m = (dr+st) / 2;
	if(x == sir[m])
	{
		poz = m;
	}
	if(x >= sir[m])
	{
		while(x >= sir[m])
		{
			poz = m;
			m++;
		}
	}
	else 
	{
		while (x != sir[m])
		{
			m--;
		}
		poz = m;
	}

}
void caut1(int st, int dr, int x, int &poz)
{
	int m = (st + dr) / 2;
	if (x == sir[m])
		poz = m;
		if (x >= sir[m])
		{
			while (x >= sir[m])
			{
				poz = m;
				m++;
			}
		}
		else
		{
			while (x < sir[m])
			{
				m--;
			}
			poz = m;
		}
}
void caut2(int st, int dr, int x, int &poz)
{
	int m = (st + dr) / 2;
	if (x == sir[m])
		poz = m;
	if (x <= sir[m])
	{
		while (x <= sir[m])
		{
			poz = m;
			m--;
		}
	}
	else
	{
		while (x > sir[m])
		{
			m++;
		}
		poz = m;
	}
}
int main()
{	
	FILE *f = fopen("cautbin.in", "r");
	fscanf(f, "%d", &n);
	//sir = new long long int[n+1];
	for (int i=1; i<=n; i++)
		fscanf(f, "%d", &sir[i]);
	fscanf(f, "%d", &m);
	//cerinte = new long long int[m+1];	

	FILE *g = fopen("cautbin.out", "w"); 
	for(int i=1; i<=m; i++)
	{
		int a, val;
		fscanf(f, "%d %d", &a, &val);
		if (a == 0)
		{
			poz = 0;
			caut0(1, n, val, poz);
			fprintf(g, "%d\n", poz);
		}
		else
			if (a == 1)
			{
				poz = 0;
				caut1(1, n, val, poz);
				fprintf(g, "%d\n", poz);
			}
			else
			{
				poz = 0;
				caut2(1, n, val, poz);
				fprintf(g, "%d\n", poz);
			}
	}
	fclose(g);
	fclose(f);
	return 0;
}