#include <fstream>
#include <algorithm>

using namespace std;

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

long long i, n, m, x, y, v[100001], r;

int main()
{   f >> n;
    for ( i = 1; i <= n; i++ ){
        f >> v[i];
    }
    f >> m;
    for ( i = 1; i <= m; i++ ){
        f >> x >> y;
        if ( x == 0 ){
            r = upper_bound ( v + 1, v + n + 1, y ) - v - 1;
            if ( v[r] != y )
                g << "-1" << "\n";
            else
                g << r << "\n";
        }
        else if ( x == 1 ){
            r = upper_bound ( v + 1, v + n + 1, y ) - v - 1;
            if ( v[r] != y )
                g << r - 1 << "\n";
            else
                g << r << "\n";
        }
        else {
            r = lower_bound ( v + 1, v + n + 1, y ) - v;
                g << r << "\n";
        }
    }


    return 0;
}