#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main()
{
    ifstream inputFile("cautbin.in");
    ofstream outputFile("cautbin.out");

    int nLength = 0;
    inputFile >> nLength;

    vector<int> arrElements(nLength);

    for(int i = 0; i < nLength; ++i)
    {
        inputFile >> arrElements[i];
    }

    int nOperations = 0;

    inputFile >> nOperations;

    for(int i = 0; i < nOperations; ++i)
    {
        int nCase = -1, nValue = 0;
        inputFile >> nCase >> nValue;

        int nLeft = 0, nRight = nLength - 1;

        while(nRight - nLeft > 1)
        {
            const int nMiddle = (nLeft + nRight) / 2; // medie aritmetica..
            if(nCase != 2)
            {
                if(arrElements[nMiddle] < nValue)
                {
                    nRight = nMiddle - 1;
                }
                else
                {
                    nLeft = nMiddle;
                }
            }
            else
            {
               if(arrElements[nMiddle] <= nValue)
                {
                    nRight = nMiddle;
                }
                else
                {
                    nLeft = nMiddle + 1;
                }
            }
        }

        switch(nCase)
            {
                case 0:
                    if(arrElements[nRight] == nValue)
                    {
                        outputFile << nRight + 1;
                        break;
                    }
                    if(arrElements[nLeft] == nValue)
                    {
                        outputFile << nLeft + 1;
                        break;
                    }
                    outputFile << -1;
                    break;
                case 1:
                    if(arrElements[nLeft] <= nValue)
                    {
                        outputFile << nLeft + 1;
                        break;
                    }
                    if(arrElements[nRight] <= nValue)
                    {
                        outputFile << nRight + 1;
                        break;
                    }
                    outputFile << -1;
                    break;
                case 2:
                    if(arrElements[nLeft] >= nValue)
                    {
                        outputFile << nLeft + 1;
                        break;
                    }
                    if(arrElements[nRight] >= nValue)
                    {
                        outputFile << nRight + 1;
                        break;
                    }
                    outputFile << -1;
                    break;
            }

            outputFile << '\n';
    }





    return 0;
}