#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int main()
{
    int n, v[100005], m;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i];

    cin >> m;
    for(int q = 1; q <= m; q++)
    {
        int k, x;
        cin >> k >> x;
        
        int st = 1, dr = n, poz = -1;

        if(k == 0)
        {
            while(st <= dr)
            {
                int mid = st + (dr - st) / 2;
                if(v[mid] == x)
                {
                    poz = mid;
                    st = mid + 1;
                }
                else if(v[mid] < x)
                {
                    st = mid + 1;
                }
                else
                {
                    dr = mid - 1;
                }
            }
            cout << poz << '\n';
        }
        else if(k == 1)
        {
            while(st <= dr)
            {
                int mid = st + (dr - st) / 2;
                if(v[mid] <= x)
                {
                    poz = mid;
                    st = mid + 1; 
                }
                else
                {
                    dr = mid - 1;
                }
            }
            cout << poz << '\n';
        }
        else if(k == 2)
        {
            while(st <= dr)
            {
                int mid = st + (dr - st) / 2;
                if(v[mid] >= x)
                {
                    poz = mid;
                    dr = mid - 1; 
                }
                else
                {
                    st = mid + 1;
                }
            }
            cout << poz << '\n';
        }
    }

    return 0;
}