#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 = 0;
    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;
}

int main()
{
    v.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++)
    {
        int nr_int, val;
        cin >> nr_int >> val;
        if(nr_int == 0)
        {
            int nr;
            nr = caut_bin1(1, n, val);
            if(v[nr] == val)
            {
                cout << nr << '\n';
            }
            else 
            {
                cout << "-1" << '\n';
            }
        }
        else if(nr_int == 1)
        {
            cout << caut_bin1(1, n, val) << '\n';
        }
        else 
        {
            cout << caut_bin2(1, n, val) << '\n';
        }
    }
    return 0;
}