#include <stdio.h>

#define IN "cautbin.in"
#define OUT "cautbin.out"
#define N 100001
#define NF -1

static unsigned long v[N], n;

static long cautbin_0(long);
static long cautbin_1(long);
static long cautbin_2(long);

int main(void) {

long i, m, x;
int q;

(void) freopen(IN, "r", stdin);
(void) freopen(OUT, "w", stdout);

(void) scanf("%ld", &n);
for(i = 1; i <= n; ++i) (void) scanf("%ld", &v[i]);

(void) scanf("%ld", &m);

while(m--) {

(void) scanf("%d %ld", &q, &x);

switch(q) {

case 0:
printf("%ld\n", cautbin_0(x));
break;

case 1:
printf("%ld\n", cautbin_1(x));
break;

case 2:
printf("%ld\n", cautbin_2(x));
break;
}
}

return 0;
}

long cautbin_0(long x) {

long st = 0, dr = n, mid;

do {

mid = st + (dr - st) / 2;

if(x < v[mid]) dr = mid - 1;
else st = mid + 1;
} while(v[mid] != x && st <= dr);

if(v[mid] != x) return NF;
else while(v[mid + 1] == x) ++mid;

return mid;
}

long cautbin_1(long x) {

long st = 0, dr = n, mid;

do {

mid = st + (dr - st) / 2;

if(x < v[mid]) dr = mid - 1;
else st = mid + 1;
} while(v[mid] != x && st <= dr);

if(v[mid] > x) --mid;
if(v[mid] == x) while(v[mid + 1] == x && mid < n) ++mid;

return mid;
}

long cautbin_2(long x) {

long st = 0, dr = n, mid;

do {

mid = st + (dr - st) / 2;

if(x < v[mid]) dr = mid - 1;
else st = mid + 1;
} while(v[mid] != x && st <= dr);

if(v[mid] < x) ++mid;
if(v[mid] == x) while(v[mid - 1] == x && mid > 0) --mid;

return mid;
}