#include <fstream>

using namespace std;

int n, i, m, mode, mid, tmp;
long int x;
long int sir[100000];

int bin_search_0(int beg, int end);
int bin_search_1(int beg, int end);
int bin_search_2(int beg, int end);

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

    fin >> n;

    for (i=0; i<n; i++)
    {
        fin >> sir[i];
    }

    fin >> m;

    for (i=0; i<m; i++)
    {
        fin >> mode;
        fin >> x;
        switch (mode)
        {
        case 0:
            fout << bin_search_0(0, n-1) << "\n";
            break;
        case 1:
            fout << bin_search_1(0, n-1) << "\n";
            break;
        case 2:
            fout << bin_search_2(0, n-1) << "\n";
            break;
        }
    }

    fin.close();
    fout.close();

    return 0;
}

int bin_search_0(int beg, int end)
{
    tmp=-2;
    while (beg<=end)
    {
        mid=beg+(end-beg)/2;
        if (sir[mid]>x)
        {
            end=mid-1;
        }
        else if (sir[mid]<x)
        {
            beg=mid+1;
        }
        else
        {
            tmp=mid;
            beg=mid+1;
        }
    }
    return tmp+1;
}

int bin_search_1(int beg, int end)
{
    tmp=-2;
    while (beg<=end)
    {
        mid=beg+(end-beg)/2;
        if (sir[mid]>x)
        {
            end=mid-1;
        }
        else
        {
            tmp=mid;
            beg=mid+1;
        }
    }
    return tmp+1;
}

int bin_search_2(int beg, int end)
{
    tmp=-2;
    while (beg<=end)
    {
        mid=beg+(end-beg)/2;
        if (sir[mid]<x)
        {
            beg=mid+1;
        }
        else
        {
            tmp=mid;
            end=mid-1;
        }
    }
    return tmp+1;
}