#include <fstream>

using namespace std;

#define Nmax 100000

int v[Nmax];

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");

    int n, m, i, cer, x, l, r, mid, sol;

    fin >> n;

    for(i = 0; i < n; i++)
    {
        fin >> v[i];
    }

    fin >> m;

    for(i = 0; i < m; i++)
    {
        fin >> cer >> x;

        l = 0;
        r = n - 1;

        if(cer == 0)
        {
            sol = -2;
            while(l <= r)
            {
                mid = (l + r) / 2;
                if(x >= v[mid])
                {
                    if(x == v[mid])
                    {
                        sol = mid;
                    }
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }
        }
        else if(cer == 1)
        {
            while(l <= r)
            {
                mid = (l + r) / 2;
                if(x >= v[mid])
                {
                    sol = mid;
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }
        }
        else if(cer == 2)
        {
            while(l <= r)
            {
                mid = (l + r) / 2;
                if(x <= v[mid])
                {
                    sol = mid;
                    r = mid - 1;
                }
                else
                {
                    l = mid + 1;
                }
            }
        }

        fout << sol + 1 << '\n';
    }
    return 0;
}