#include <stdio.h>
#include <assert.h>
 
int N, M, v[100005];
 
inline int BS1(int x)
{
    int lo, hi, mid;
 
    for (lo = 1, hi = N; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (x < v[mid]) hi = mid-1;
        else if (v[mid] < x) lo = mid+1;
        else return mid;
    }
    return -1;
}
 
inline int BS2(int x)
{
    int lo, hi, mid, last = 0;
 
    for (lo = 1, hi = N; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (v[mid] <= x) last = mid, lo = mid+1;
        else hi = mid-1;
    }
    return last;
}
 
inline int BS3(int x)
{
    int lo, hi, mid, last = N+1;
 
    for (lo = 1, hi = N; lo <= hi; )
    {
        mid = lo + (hi-lo) / 2;
        if (x <= v[mid]) last = mid, hi = mid-1;
        else lo = mid+1;
    }
    return last;
}
 
int main(void)
{
    int i, t, 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);
    for (; M; --M)
    {
        scanf("%d %d", &t, &x);
        if (!t)
            printf("%d\n", BS1(x));
        else if (t == 1)
            printf("%d\n", BS2(x));
        else
            printf("%d\n", BS3(x));
    }
}