#include <iostream>
#include <fstream>
using namespace std;
int n,i,v[100005],st,dr,x,t,m,k,m1,sol;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main()
{
    in>>n;
    for (i=1;i<=n;i++)
        in>>v[i];
    in>>m1;
    for (i=1;i<=m1;i++)
    {
        in>>t>>x;
        if (t==0)
        {
            sol=-1;
            st=1;
            dr=n;
            k=0;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (v[m]==x)
                {
                    k=1;
                    sol=m;st=m+1;

                }
                else if (v[m]<x) st=m+1;
                else dr=m-1;
            }
            out<<sol<<"\n";

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

                else st=m+1;

            }out<<sol<<"\n";
        }
        else if (t==1)
        {
            st=1;dr=n;
            while (st<=dr)
            {
                m=(st+dr)/2;
                if (v[m]<=x)
                {
                    sol=m;st=m+1;
                }
                else dr=m-1;

            }
            out<<sol<<"\n";
        }
    }
}