#include <stdio.h>
#include <stdlib.h>
#define N 100010
int vector[N];
 
int Cautbin0 (int primul, int ultimul, int val) {
    int mijloc;
 
    while (primul <= ultimul) 
	{
        mijloc = (primul + ultimul) / 2;
        if (vector[mijloc] <= val)
            primul = mijloc + 1;
        else
            ultimul = mijloc - 1;
    }
    mijloc = (primul + ultimul) / 2;
 
    if (vector[mijloc] > val)
		mijloc --;
    if (vector[mijloc] == val)
        return mijloc;
    return -1;
}
 
int Cautbin1 (int primul, int ultimul, int val) {
    int mijloc, n = ultimul;
 
    while (primul < ultimul){
        mijloc = (primul + ultimul) / 2;
        if (vector[mijloc] <= val)
            primul = mijloc + 1;
        else
            ultimul = mijloc;
    }
 
    mijloc = (primul + ultimul) / 2;
    if (vector[mijloc] > val)
       -- mijloc;
    return mijloc;
}
 
int Cautbin2 (int primul, int ultimul, int val) {
    int mijloc;
 
    while (primul < ultimul) {
        mijloc = (primul + ultimul) / 2;
        if (vector[mijloc] < val)
            primul = mijloc + 1;
        else
            ultimul = mijloc;
    }
     
    mijloc = (primul + ultimul) / 2;
    if (vector[mijloc] < val)
       ++ mijloc;
    return mijloc;
}
 
int main () {
    int i, n, m, tip, x;
 
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &vector[i]);
     
    scanf("%d", &m);
 
    while (m --){
          scanf("%d%d", &tip, &x);
          if (tip == 0)
             printf("%d\n", Cautbin0(1, n, x));
          if (tip == 1)
             printf("%d\n", Cautbin1(1, n, x));
          if (tip == 2)
             printf("%d\n", Cautbin2(1, n, x));
    }
    exit(0);
}