#include <fstream>
#include <cstdio>
using namespace std;
int n,i,a,b,m,v[100010],p,u,M;
int main()
{
    freopen("cautbin.in","r",stdin);
    ofstream g ("cautbin.out");
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d",&v[i]);
    scanf("%d",&M);
    for(i=1; i<=M; i++)
    {
        scanf("%d%d",&a,&b);
        p=1;
        u=n;
        if(a==0)
        {
            m=(p+u)/2;
            while(p<u)
            {
                if(v[m]<=b)p=m+1;
                else if(v[m]>b)u=m-1;
                m=(p+u)/2;
            }
            if(v[m]>b)m--;
            if(v[m]==b)g<<m<<'\n';
            else g<<-1<<'\n';
        }
        else
            if(a==1)
        {
            m=(p+u)/2;
            while(p<u)
            {
                if(v[m]<=b)p=m+1;
                else if(v[m]>b)u=m-1;
                m=(p+u)/2;
            }
        if(v[m]>b)m--;
            g<<m<<'\n';
        }
         else
        {
            m=(p+u)/2;
            while(p<u)
            {
                if(v[m]<b)p=m+1;
                else if(v[m]>=b)u=m-1;
                m=(p+u)/2;
            }
        if(v[m]<b)m++;
            g<<m<<'\n';
        }
    }
    return 0;
}