#include <fstream>
#include <vector>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int binarySearch(vector<int> &v, int n, int numar, int metoda);

int main()
{
    int n, x;
    vector <int> v;
    fin >> n;
    for(int i = 0; i < n; i++)
    {    
        fin >> x;
        v.push_back(x);
    }
    int m, metoda, numar;
    fin >> m;
    for(int j = 0; j < m; j++)
    {
        fin >> metoda >> numar;
        fout << binarySearch(v, n, numar, metoda) + 1 << '\n';
    }

    return 0;
}



int binarySearch(vector<int> &v, int n, int numar, int metoda)
{
    int left = 0;
    int right = n - 1;
    int i = -2;

    while (left <= right)
    {
        int middle = (left + right) / 2;

        switch (metoda)
        {
        case 0:
            if(v[middle] == numar)
                i = middle;
            if(v[middle] > numar)
                right = middle - 1;
            else
                left = middle + 1;
            break;
        case 1:
            if(v[middle] <= numar)
                i = middle;
            if(v[middle] > numar)
                right = middle - 1;
            else 
                left = middle + 1;
            break;
        case 2:
            if(v[middle] >= numar)
                i = middle;
            if(v[middle] >= numar)
                right = middle - 1;
            else
                left = middle + 1;
            break;
        default:
            break;
        }
    }
    return i;
}