#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int st,dr,n,a,b,m2,m,i,t,v[100001],j,x;

int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>v[i];
f>>m2;
st=1;dr=n;
for( i=1; i<=m2; i++)
{


        f>>t>>x;
        if(t==0){
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(x>=v[m])
                    st=m+1;
                else
                    dr=m-1;
            }
            m=(st+dr)/2;
            if(v[m]==x)
                g<<m<<'\n';
            else
               g<<-1<<'\n';
        }
        else if(t==1){
            while(st<dr){
                m=(st+dr)/2;
                if(x>=v[m])
                    st=m+1;
                else
                    dr=m;
            }
            m=(st+dr)/2;
            if(v[m]>x)
                --m;
           g<<m<<'\n';
        }
        else{
            while(st<dr){
                m=(st+dr)/2;
                if(x>v[m])
                    st=m+1;
                else
                    dr=m;
            }
            m=(st+dr)/2;
            if(v[m]<x)
                ++m;
           g<<m<<'\n';
        }
        st=1;
        dr=n;
    }

    return 0;
}