#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int main()
{
    long long int st, dr, n, m, i, x, k;
    int v[100000], gasit, rasp, p;
    f >> n;
    for (i=1; i<=n; i++)
        f >> v[i];
    f >> k;
    for (i=1; i<=k; i++)
    {
        f >> p >> x;
        if (p==0)
        {
            st=1, dr=n, gasit=0;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (v[m]==x)
                    rasp=m, st=m+1, gasit=1;
                else if (v[m]<x)
                    st=m+1;
                else dr=m-1;
            }
            if (gasit)
                g << rasp << "\n";
            else g << -1;
        }
        else if (p==1)
        {
            st=1, dr=n;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (v[m]<=x)
                    rasp=m, st=m+1;
                else dr=m-1;
            }
            g << rasp << "\n";
        }
        else
        {
            st=1, dr=n;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (v[m]>=x)
                    rasp=m, dr=m-1;
                else st=m+1;
            }
            g << rasp << "\n";
        }
    }
    return 0;
}