#include <stdio.h>
#include <stdlib.h>
#define N 100010
int v[N];

int bsearch0 (int p, int u, int key) {

int m;

while (p <= u) {
m = (p + u) / 2;
if (v[m] <= key)
p = m + 1;
else
u = m - 1;
}
m = (p + u) / 2;

if (v[m] > key) m --;
if (v[m] == key)
return m;
return -1;

int bsearch1 (int p, int u, int key) {
int m, n = u;

while (p < u){
m = (p + u) / 2;
if (v[m] <= key)
p = m + 1;
else
u = m;
}

m = (p + u) / 2;
if (v[m] > key)
-- m;
return m;
}

int bsearch2 (int p, int u, int key) {
int m;

while (p < u) {
m = (p + u) / 2;
if (v[m] < key)
p = m + 1;
else
u = m;
}

m = (p + u) / 2;
if (v[m] < key)
++ m;
return m;
}

int main () {
int i, n, m, tip, val;

freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d", &n);
for (i = 1; i <= n; ++ i)
scanf("%d", &v[i]);

scanf("%d", &m);

while (m --){
scanf("%d%d", &tip, &val);
if (tip == 0)
printf("%d\n", bsearch0(1, n, val));
if (tip == 1)
printf("%d\n", bsearch1(1, n, val));
if (tip == 2)
printf("%d\n", bsearch2(1, n, val));
}
exit(0);
}