#include <iostream>
#include <fstream>

using namespace std;

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

void read(int* v, int n)
{
    for(int i = 0; i < n; i++)
        in >> v[i];
}

int solve(int* v, int n, int x, int t)
{
    int li = 0, ls = n-1, m;
    bool exists = true;
    while(ls >= li)
    {
        m = li + (ls - li) / 2;
        if(v[m] == x)
        {
            break;
        }
        else if(v[m] > x)
        {
            ls = m - 1;
        }
        else
        {
            li = m + 1;
        }
    }

    if(t == 0)
    {
        if(v[m] != x)
        {
            return -1;
        }
        while(m < n - 1)
        {
            if(v[m+1] == x)
            {
                m++;
            }
            else
            {
                break;
            }
        }
        return m+1;
    }
    else if(t == 1)
    {
        if(v[m] > x)
        {
            m--;
        }
        while(v[m+1] <= x && m < n-1)
        {
            m++;
        }
        return m+1;
    }
    else
    {
        if(v[m] < x)
        {
            m++;
        }
        while(v[m-1] >= x && m > 0)
        {
            m--;
        }
        return m+1;
    }
}



int main()
{
    int n, m, t, x;
    in >> n;
    int* v = new int[n];
    read(v, n);
    in >> m;
    for(int i = 0; i < m; i++)
    {
        in >> t >> x;
        out << solve(v, n, x, t) << "\n";
    }

    return 0;
}