#include <fstream>

using namespace std;

int values[1000001];

int binarySearch (int x, int n)
{
    int position = 0;
    for(int power = 20; power >= 0; power-- )
    {
        if(position + (1 << power) <= n && values[position + (1 << power)] <= x)
            position += (1 << power);
    }
    return position;
}

int solve(int valoare, int x, int n)
{
    if (valoare == 0)
    {
        return ((values[binarySearch(x, n)] == x && binarySearch(x, n) != 0) ? binarySearch(x, n) : -1);
    }
    if (valoare == 1)
    {
        return binarySearch(x, n);
    }
    return binarySearch(x - 1, n) + 1;
}

int main() {
    ifstream inputfile("cautbin.in");
    ofstream outputfile("cautbin.out");

    int n, m;
    inputfile >> n;
    for (int i = 1; i <= n; i++) {
        inputfile >> values[i];
    }
    inputfile >> m;
    for (int i = 1; i<= m; i++)
    {
        int valoare, x;
        inputfile >> valoare >> x;
        outputfile << solve(valoare, x, n) << "\n";
    }


    return 0;
}