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

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

typedef struct {
	int pos;
	int lpos;
} globals;
globals gl = { 0 };

int FindNumber0(int *vector, int vsize, int target)
{
	
	while (true) {
		if (vector[gl.pos] < target) {
			gl.pos--;
		} else {
			if (vector[gl.pos] == target) {
				if (gl.lpos < gl.pos) {
					gl.lpos = gl.pos;
					return gl.pos;
				}
			}
			gl.pos++;
		}
		if (vsize - 1 == gl.pos) {
			break;
		}
	}
	return -2;
}

int FindNumber1(int *vector, int vsize, int target)
{

	while (true) {
		if (vector[gl.pos] < target) {
			gl.pos--;
		} else {
			if (vector[gl.pos] <= target) {
				if (gl.lpos < gl.pos) {
					gl.lpos = gl.pos;
					return gl.pos;
				}
			}
			gl.pos++;
		}
		if (vsize - 1 == gl.pos) {
			break;
		}
	}
	return -2;
}

int FindNumber2(int *vector, int vsize, int target)
{
	for (int i = 0; i < vsize; i++) {
		if (vector[i] <= target) {
			return i;
		}
	}
	return -2;
}

int main()
{
	FILE *file = fopen("cautbin.in", "rt");
	FILE *out = fopen("cautbin.out", "wt");
	int *vector = NULL;
	int lng = 0;
	int questions = 0;
	int answer = 0, response = 0;
	int target = 0;
	short ID = 0;
	bool found = 0;
	fscanf(file, "%ld ", &lng);
	vector = (int *)malloc(lng * sizeof(int));
	for (int i = 0; i < lng; i++) {
		fscanf(file, "%ld ", &vector[i]);
	}
	fscanf(file, "%ld ", &questions);
	for (int i = 0; i < questions; i++) {
		fscanf(file, "%ld ", &ID);
		answer = 0;
		response = 0;
		gl.lpos = 0;
		if (ID == 0) {
			fscanf(file, "%ld ", &target);
			gl.pos = lng / 2;
			while (answer != -2) {
				response = answer;
				answer = FindNumber0(vector, lng, target); 
			}
			fprintf(out, "%ld\r\n", response + 1);
		}
		if (ID == 1) {
			fscanf(file, "%ld ", &target);
			gl.pos = lng / 2;
			while (answer != -2) {
				response = answer;
				answer = FindNumber1(vector, lng, target);
			}
			fprintf(out, "%ld\r\n", response + 1);
		}
		if (ID == 2) {
			response = FindNumber2(vector, lng, target);
			fprintf(out, "%ld\r\n", response + 1);
		}
	}
	return 0;
}