#include <stdio.h>
#include <string.h>
#define N 100001

using namespace std;

int i, n, m, t, x, v[N];

int cb(int x, int l, int r)
{
    int mid, p = -1;
    if(!t)
    {
        while(l <= r)
        {
            mid = l + (r - l) / 2;
            if(v[mid] == x) p = mid;
            if(v[mid] <= x) l = mid + 1;
            if(v[mid] > x) r = mid - 1;
        }
    }
    else
        if(t == 1)
            while(l <= r)
            {
                mid = l + (r - l) / 2;
                if(v[mid] <= x) {l = mid + 1; p = mid;}
                else r = mid - 1;
            }
    else
        while(l <= r)
        {
            mid = l + (r - l) / 2;
            if(v[mid] >= x) {r = mid - 1; p = mid;}
            else l = mid + 1;
        }
    return p;
}

int main()
{
    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);
    for(i = 0; i < m; i++)
    {
        scanf("%d%d", &t, &x);
        printf("%d\n", cb(x, 1, n));
    }
}