#include <iostream>
#include <fstream>
using namespace std;
long long int n,m,i,v[100000],x,a,mid,st,dr,in;
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for(i=1; i<=n; i++)
        fin>>v[i];
    fin>>m;
    for(i=1; i<=m; i++)
    {
        fin>>a>>x;
        if(a==0)
        {
            in=-1;
            st=1;
            dr=n;
            while(st<=dr)
            {
                mid=(st+dr)/2;

                if(st==dr)
                {
                    if(v[mid]==x)
                        in=mid;
                    st++;
                }
                else if(v[mid]<x)
                {
                    st=mid+1;
                }
                else if(v[mid]>x)
                {
                    dr=mid-1;
                }


                else if(v[mid]==x)
                {
                    in=mid;
                    st=mid;
                    if (st+1==dr)
                    {
                        st++;
                    }
                }
            }
            fout<<in<<endl;
        }
        else if(a==1)
        {
            in=-1;
            st=1;
            dr=n;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(v[mid]<=x)
                {
                    in=mid;
                    st=mid+1;
                }
                else
                    if(v[mid]>x)
                {
                    dr=mid-1;
                }

            }
            fout<<in<<endl;
        }
        else if(a==2)
        {
            in=-1;
            st=1;
            dr=n;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(v[mid]>=x)
                {
                    in=mid;
                    dr=mid-1;
                }
                else
                    if(v[mid]<x)
                {
                    st=mid+1;
                }
            }
            fout<<in<<endl;
        }

    }
    return 0;
}