#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100100],i,j,n,m,x,y,z,t,st,dr,mij;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>t>>x;
        st=1;
        dr=n;
        y=0;
        if(t==0)
        {
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(x<v[mij])
                    dr=mij-1;
                else
                    st=mij+1;
            }
            mij=(dr+st)/2;
            if(v[mij]>x)
                mij--;
            if(x==v[mij])
                g<<mij<<'\n';
            else
                g<<"-1"<<'\n';
        }
        else
            if(t==1)
            {
                while(st<=dr)
                {
                    mij=(st+dr)/2;
                    if(v[mij]<=x)
                        st=mij+1;
                    else
                        dr=mij-1;
                }
                mij=(dr+st)/2;
                if(v[mij]>x)
                    mij--;
                if(x>=v[mij])
                    g<<mij<<'\n';
            }
            else
            {
                while(st<=dr)
                {
                    mij=(st+dr)/2;
                    if(v[mij]<x)
                        st=mij+1;
                    else
                        dr=mij-1;
                }
                mij=(dr+st)/2;
                if(v[mij]<x)
                    mij++;
                if(x<=v[mij])
                    g<<mij<<'\n';
            }
    }
    return 0;
}