#include <cstdio>   
  
const int maxn = 100001;   
  
FILE *in = fopen("cautbin.in","r"), *out = fopen("cautbin.out","w");   
  
int n, m;   
int a[maxn];   
  
void read()   
{   
    fscanf(in, "%d", &n);   
  
    for ( int i = 1; i <= n; ++i )   
        fscanf(in, "%d", &a[i]);   
}   
  
int search1(int what)   
{   
    int st = 1, dr = n, m = 0;   
  
    while ( st <= dr )   
    {   
        m = st + ((dr - st) >> 1);   
  
        if ( a[m] > what )   
            dr = m - 1;   
        else if ( a[m] < what )   
            st = m + 1;   
        else   
            return m;   
    }   
  
    return -1;   
}   
  
int search2(int what)   
{   
    int st = 1, dr = n, m = 0;   
    int answ = 0;   
  
    while ( st <= dr )   
    {   
        m = st + ((dr - st) >> 1);   
  
        if ( a[m] <= what )   
            st = m + 1, answ = m;   
        else   
            dr = m - 1;   
    }   
  
    return answ;   
}   
  
int search3(int what)   
{   
    int st = 1, dr = n, m = 0;   
    int answ = 0;   
  
    while ( st <= dr )   
    {   
        m = st + ((dr - st) >> 1);   
  
        if ( a[m] >= what )   
            dr = m - 1, answ = m;   
        else   
            st = m + 1;   
    }   
  
    return answ;   
}   
  
int main()   
{   
    read();   
  
    fscanf(in, "%d", &m);   
  
    int x, y;   
    for ( int i = 1; i <= m; ++i )   
    {   
        fscanf(in, "%d %d", &x, &y);   
  
        if ( x == 0 )   
            fprintf(out, "%d\n", search1(y));   
        else if ( x == 1 )   
            fprintf(out, "%d\n", search2(y));   
        else   
            fprintf(out, "%d\n", search3(y));   
    }   
  
    return 0;   
}