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