#include <fstream>

using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
const int N = 100000;
int v[N + 1];
int main()
{
    int n, m, i, st, dr, mij, tip, x;
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    cin >> m;
    for(i = 0; i < m; i++)
    {
        cin >> tip >> x;
        if(tip == 0)
        {
            st = 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(v[mij] <= x)
                {
                    st = mij + 1;
                }
                else
                {
                    dr = mij - 1;
                }
            }
            if(v[st - 1] == x)
                cout << st - 1 << "\n";
            else
                cout << "-1\n";
        }
        else if(tip == 1)
        {
            st = 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(v[mij] <= x)
                {
                    st = mij + 1;
                }
                else
                {
                    dr = mij - 1;
                }
            }
            cout << st - 1 << "\n";
        }
        else
        {
            st = 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(v[mij] >= x)
                {
                    dr = mij - 1;
                }
                else
                {
                    st = mij + 1;
                }
            }
            cout << dr + 1 << "\n";
        }
    }
    return 0;
}