#include <bits/stdc++.h>

using namespace std;

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int biggest_idx( int x, vector<int>& v ){
    int ans = -1;

    int l = 0 , r = v.size() - 1, mij = (l+r)/2;

    while ( l <= r ) {
        mij = (l+r)/2;
        if ( v[mij] == x ){
            ans = mij;
            l = mij + 1;
        }
        else if ( v[mij] < x )
            l = mij + 1;
        else
            r = mij - 1;
    }

    return ans+1;

}

int lowest_idx( int x, vector<int>& v ){
    int ans = -1;

    int l = 0 , r = v.size() - 1, mij = (l+r)/2;

    while ( l <= r ) {
        mij = (l+r)/2;
        if ( v[mij] <= x ){
            ans = mij;
            l = mij + 1;
        }
        else
            r = mij - 1;
    }

    return ans+1;

}

int upper_idx( int x, vector<int>& v ){
    int ans = -1;

    int l = 0 , r = v.size() - 1, mij = (l+r)/2;

    while ( l <= r ) {
        mij = (l+r)/2;
        if ( v[mij] >= x ){
            ans = mij;
            r = mij - 1;
        }
        else
            l = mij + 1;
    }

    return ans+1;

}


int main()
{
    int n,m,op,x;

    f>>n;
    vector<int> v(n,0);

    for ( int i = 0 ; i < n ; i++ )
        f>>v[i];

    f>>m;

    for ( int i = 0 ; i < m ; i++ ){
        f>>op>>x;
        if ( op == 0 )
            g << biggest_idx(x,v);
        else if ( op == 1 )
            g << lowest_idx(x,v);
        else g << upper_idx(x,v);

        g<<'\n';
    }

    return 0;
}