#include <stdio.h>
#include <algorithm>
#define IN "cautbin.in"
#define OUT "cautbin.out"
#define Lg 100001

using namespace std;

int N, M;
int A[Lg];
int C, x;

int main ()
{
    freopen (IN ,"r", stdin);
    freopen (OUT ,"w", stdout);
    scanf ("%d",&N);
    for (int i=1;i<=N;i++)
        scanf ("%d",&A[i]);

    scanf ("%d",&M);
    while (M--)
    {
        scanf ("%d %d",&C, &x);
        switch (C)
        {
            case 0: printf("%d\n",  A[upper_bound(A+1,A+N+1,x)-A-1] != x ?-1 :upper_bound(A+1,A+N+1,x)-A-1); break;
            case 1: printf("%d\n",  upper_bound(A+1,A+N+1,x)-A-1); break;
            default: printf("%d\n", lower_bound(A+1,A+N+1,x)-A); break;
        };
    }
}