#include <stdio.h>
#include <stdlib.h>

int N, M;
int *v;

int search (int *v, int N, int x, int type);

void go(void)
{
	int i, type, x;
	
	FILE *f = fopen("cautbin.in", "r");
	if (!f) 
		return;
	
	fscanf(f, "%d", &N);
	
	v = malloc(N * sizeof(int));
	if (!v) 
		return;
	for (i = 0; i < N; i++) 
		fscanf(f, "%d", &v[i]);
	
	fscanf(f, "%d", &M);
	
	for (i = 0; i < M; i++) {
		fscanf(f, "%d %d", &type, &x);
		search(v, N, x, type);
	}
}
int bsearch_1(int *v, int start, int stop, int x)
{
	int mid;
	
	if (start > stop) 
		return -1;
	mid = start + (stop - start)/2 ;
	
	
	printf("Caut bin %d , crt %d <- mid %d [%d - %d]\n", x, v[mid], mid, start, stop);

	if (v[mid] == x)
		return mid;
	else if (v[mid] < x) 
		return bsearch_1(v, mid + 1, stop, x);
	else
		return bsearch_1(v, start, mid - 1, x);
}
 

int bsearch_2(int *v, int start, int stop, int x)
{
	int mid;
	if (start >= stop) 
		return stop;
		
	mid = start + (stop - start) / 2;
	
	if (v[mid] == x) 
		return mid;
	
	else if (v[mid] < x) 
		return bsearch_2(v, mid + 1, stop, x);
	else
		return bsearch_2(v, start, mid - 1, x);
}


int search(int *v, int N, int x, int type)
{
	int pos;
	FILE *f = fopen("cautbin.out", "w");

	switch(type) {
	case 0:
		pos = bsearch_1(v, 0, N-1, x);
		printf("Found %d at %d\n", x, pos);
		
		while( pos < N-1 && v[pos + 1] == x)
			pos++;
		fprintf(f, "%d", pos);
			
		break;
	case 1:
		pos = bsearch_2(v, 0, N-1, x);
		while (pos >= 0 && v[pos] > x)
			pos--;
		fprintf(f, "%d", pos);
	case 2:
		pos = bsearch_2(v, 0, N-1, x);
		while (pos <  N && v[pos] < x) 
			pos++;
		fprintf(f, "%d", pos);
	default:
		break;
	}
}




int main(void)
{
	go();

	return 0;
}