#include <cstdio>

int N, A[100005];

int binary_search0(int x, int lo, int hi) {
    int mid;
    if (hi - lo > 1) {
      mid = (lo + hi) / 2;
      if (A[mid] <= x)
        return binary_search0(x, mid, hi);
       else
        return binary_search0(x, lo, mid);
    }
    if (lo == -1 || A[lo] != x)
        return -1;
    else
        return lo;
}

int binary_search1(int x, int lo, int hi) {
    int mid;
    if (hi - lo > 1) {
      mid = (lo + hi) / 2;
      if (A[mid] <= x)
        return binary_search1(x, mid, hi);
       else
        return binary_search1(x, lo, mid);
    }
    return lo;
}

int binary_search2(int x, int lo, int hi) {
    int mid;
    if (hi - lo > 1) {
      mid = (lo + hi) / 2;
      if (A[mid] < x)
        return binary_search2(x, mid, hi);
       else
        return binary_search2(x, lo, mid);
    }
    return hi;
}

int main(){

	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);

	int j, x, m, aux;
	scanf("%d",&N);
	for(j=1; j<=N; ++j)
		scanf("%d",&A[j]);

	scanf("%d",&m);
	for(;m--;){
		scanf("%d %d",&aux, &x);
		if(aux==0) printf("%d\n",binary_search0(x, 0, N + 1));
		if(aux==1) printf("%d\n",binary_search1(x, 0, N + 1));
		if(aux==2) printf("%d\n",binary_search2(x, 0, N + 1));
	}
}