#include <stdio.h>
#include <stdlib.h>
#define NMAX 100000

int v[NMAX];

int c_b1(int x,int a,int b)
{
    int m;

    while (a <= b) {
        m = (a + b) / 2;
        if (v[m] <= x)
            a = m + 1;
        else
            b = m - 1;
    }
    m = (a + b) / 2;

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

int c_b2(int x,int a,int b)
{
    int m;

    while (a < b){
        m = (a + b) / 2;
        if (v[m] <= x)
            a = m + 1;
        else
            b = m;
    }

    m = (a + b) / 2;
    if (v[m] > x)
       -- m;
    return m;
}

int c_b3(int x,int a,int b)
{
	int m;
	while(a<b)
	{
		m=(a+b)/2;
		if(v[m]<x)
			a=m+1;
		else
			b=m;
	}
	
	m=(a+b)/2;
	if(v[m]<x)
		m++;
	return m;
}

int main () {
    int i, n, m, op, x;

    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", &op, &x);
          if (op == 0)
             printf("%d\n", c_b1(x, 1, n));
          if (op == 1)
             printf("%d\n", c_b2(x, 1, n));
          if (op == 2)
             printf("%d\n", c_b3(x, 1, n));
    }
    exit(0);
}