#include <fstream>

using namespace std;

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

int v[100001];
int v2[100001];
int x[100001];

int main()
{
int n, m, med, rasp, st, dr, i;
fin>>n;
for(i=1; i<=n; i++)
    fin>>v[i];
fin>>m;
for(i=1; i<=m; i++)
    fin>>v2[i]>>x[i];
for(i=1; i<m; i++)
    {
    st=v[1];
    dr=v[n];
    if(v2[i]==0 || v2[i]==1)
        {
        while(st<=dr)
            {
            med=(st+dr)/2;
            if(v[med]<=x[i])
                {
                rasp=med;
                st=med+1;
                }
            else
                {
                dr=med-1;
                }
            }
        if(v2[i]==0)
            {
            if(v[rasp]==x[i]) fout<<rasp<<'\n';
            else fout<<-1<<'\n';
            }
        else fout<<rasp<<'\n';
        }
    else
        {
        while(st<=dr)
            {
            med=(st+dr)/2;
            if(v[med]>=x[i])
                {
                rasp=med;
                dr=med-1;
                }
            else
                {
                st=med+1;
                }
            }
        fout<<rasp<<'\n';
        }
    }
for(i=m; i<=m; i++)
    {
    st=v[1];
    dr=v[n];
    if(v2[i]==0 || v2[i]==1)
        {
        while(st<=dr)
            {
            med=(st+dr)/2;
            if(v[med]<=x[i])
                {
                rasp=med;
                st=med+1;
                }
            else
                {
                dr=med-1;
                }
            }
        if(v2[i]==0)
            {
            if(v[rasp]==x[i]) fout<<rasp;
            else fout<<-1;
            }
        else fout<<rasp;
        }
    else
        {
        while(st<=dr)
            {
            med=(st+dr)/2;
            if(v[med]>=x[i])
                {
                rasp=med;
                dr=med-1;
                }
            else
                {
                st=med+1;
                }
            }
        fout<<rasp;
        }
    }
return 0;
}