#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n, v[100005], i, j, m, c, x, q;
int main()
{
    fin >> n;
    for (i = 1; i <= n; i ++)
        fin >> v[i];
    fin >> m;
    for (q = 1; q <= m; q ++)
    {
        fin >> c >> x;
        i = 1;
        j = n;
        while (i < j)
        {
            int mij = (i + j) / 2;
            if (v[mij] > x)
                j = mij - 1;
            else
            {
                i = mij + 1;
                if (v[mij] == x)
                    break;
            }
        }
        if (!c)
        {
            if (v[i] == x)
            {
                while (v[i] == x)
                    i ++;
                fout << i - 1;
            }
            else
                fout << "-1";
        }
        else
        {
            if (c == 1)
            {
                while (v[i] <= x)
                    i ++;
                fout << i - 1;
            }
            else
            {
                i ++;
                while (v[i] >= x)
                    i --;
                fout << i + 1;
            }
        }
        fout << "\n";
    }
    return 0;
}