#include <stdio.h>

#include <stdlib.h>

#define N 100010

int v[N];

 

int bsearch0 (int left, int right, int key) {

int pivot;


while (left <= right) {

pivot = (left + right) / 2;

if (v[pivot] <= key)

left = pivot + 1;

else

right = pivot - 1;

}

pivot = (left + right) / 2;

 

if (v[pivot] > key) pivot --;

if (v[pivot] == key)

return pivot;

return -1;

}

 

int bsearch1 (int left, int right, int key) {

int pivot, n = right;

 

while (left < right){

pivot = (left + right) / 2;

if (v[pivot] <= key)

left = pivot + 1;

else

right = pivot;

}

 

pivot = (left + right) / 2;

if (v[pivot] > key)

-- pivot;

return pivot;

}

 

int bsearch2 (int left, int right, int key) {

int pivot;

 

while (left < right) {

pivot = (left + right) / 2;

if (v[pivot] < key)

left = pivot + 1;

else

right = pivot;

}

 

pivot = (left + right) / 2;

if (v[pivot] < key)

++ pivot;

return pivot;

}

 

int main () {

int i, n, pivot, 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", &pivot);

while (pivot --){

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));

}
return 0;

}