#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
unsigned long long a[100001];
int main()
{
    int n,m,c,inc,sf,mij;
    unsigned long long nr;
    f>>n;
    for (int i=1;i<=n;i++)
    {
        f>>a[i];
    }
    f>>m;
    for (int i=1;i<=m;i++)
    {
        f>>c>>nr;
        inc=1;sf=n;
mij=(inc+sf)/2;
        while (inc<sf)
        {

            if (a[mij]>nr){sf=mij-1;}else
                {
                    if (a[mij]<nr){inc=mij+1;}
                    else
                    {
                        inc=sf;
                    }
                }
mij=(inc+sf)/2;
        }

        if (c==0)
        {
            while (a[mij]==nr)
            {mij++;}
            if (a[mij-1]==nr) g<<mij-1<<'\n';
                else
                g<<-1<<'\n';
        }else
        if (c==1)
        {
            while ((a[mij]==nr)&&(mij<n))
            {mij++;}
            if (a[mij]>nr)mij--;
                g<<mij<<'\n';

        }else
        {
            if (a[mij]==nr)
            {
             while (a[mij]==nr)
            {mij--;}
            g<<mij+1<<'\n';
            }else
            {
                if (a[mij]>nr)
                    g<<mij<<'\n';
                else
                    g<<mij+1<<'\n';
            }

        }
    }
    return 0;
}