#include <fstream>
#include <vector>

using namespace std;

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

vector < int > v;

int caut_bin1(int st, int dr, int val)
{
    int ans = -1;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(v[st] <= val)
        {
            ans = m;
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    return ans;
}

int caut_bin2(int st, int dr, int val)
{
    int ans = -1;
    while(st <= dr)
    {
        int m = (st + dr) / 2;
        if(v[m] >= val)
        {
            dr = m - 1;
            ans = m;
        }
        else 
        {
            st = m + 1;
        }
    }
    return ans;
}

struct intr{
    int nr, val;
};

vector < intr > intrebari;

int main()
{
    v.resize(100001);
    intrebari.resize(100001);
    int n, m;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> intrebari[i].nr >> intrebari[i].val;
    }
    for(int i = 1; i <= m; i++)
    {
        if(intrebari[i].nr == 0)
        {
            cout << caut_bin1(1, n, intrebari[i].val) << '\n';
        }
        else if(v[caut_bin1(1, n, intrebari[i].val)] != intrebari[i].val)
        {
            cout << "-1" << '\n';
        }
        else if(intrebari[i].nr == 1)
        {
            cout << caut_bin1(1, n, intrebari[i].val) << '\n';
        }
        else 
        {
            cout << caut_bin2(1, n, intrebari[i].val) << '\n';
        }
    }
    return 0;
}