#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int N,M,a[100001],i,st,dr,mij,x,y;

int main()
{
    fin >> N;
    for (i=1;i<=N;++i)
    {
        fin >> a[i];
    }
    fin >> M;
    for (i=1;i<=M;++i)
    {
        fin >> x >> y;
        st=1;
        dr=N;
        if (x==0)
        {
            while (st<=dr)
            {
                mij=(st+dr)/2;
                if (a[mij]<=y)
                {
                    st=mij+1;
                }
                else
                {
                    dr=mij-1;
                }
            }
            mij=(st+dr)/2;
            if (a[mij]>y)
            {
                --mij;
            }
            if (a[mij]==y)
            {
                fout << mij;
            }
            else
            {
                fout << -1;
            }
        }
        if (x==1)
        {
            while (st<dr)
            {
                mij=(st+dr)/2;
                if (a[mij]<=y)
                {
                    st=mij+1;
                }
                else
                {
                    dr=mij;
                }
            }
            mij=(st+dr)/2;
            if (a[mij]>y)
            {
                --mij;
            }
            fout << mij;
        }
        if (x==2)
        {
            while (st<dr)
            {
                mij=(st+dr)/2;
                if (a[mij]<y)
                {
                    st=mij+1;
                }
                else
                {
                    dr=mij;
                }
            }
            if (a[mij]<y)
            {
                ++mij;
            }
            fout << mij;
        }
        fout << '\n';
    }
    return 0;
}