#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));  
    }  
}