#include <iostream>
#include <fstream>
using namespace std;
int s,d,m,x,a[100001],ni,i,j,p,c,b,st,dr;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int caut(int str,int drr)  // 0 x
{
    if(str>drr) return -1;
    else
    {
        m=(str+drr)/2;
        p=m;
        if(x==a[m])
        {
            p=m;
            return 0;
        }
        else if(a[m]<x) caut(m+1,drr);
        else caut(str,m-1);
    }
}
int main()
{
    f>>ni;
    for (i=1; i<=ni; i++)
        f>>a[i];
    f>>m;
    for(j=1; j<=m; j++)
    {
        f>>c>>x;
        if(c==0)
        {
            st=1;
            dr=ni;
            if(!caut(st,dr))
            {
                while(a[p+1]==x&&p<ni)p++;
                g<<p<<'\n';

            }
            else g<<"-1"<<'\n';

        }
        else if(c==1)
        {
            st=1;
            dr=ni;
            caut(st,dr);
            if(a[p]<=x)
            {
                while(a[p+1]<=x&&p<ni) p++;
                g<<p<<'\n';
            }
            else g<<p-1<<'\n';

        }
        else//
        {
            st=1;
            dr=ni;
            if(!caut(st,dr))
            {
                while(a[p-1]==x&&p>1)p--;
                g<<p<<'\n';
            }
            else
            {
                st=1;
                dr=ni;
                caut(st,dr);
                while(a[p]<x&&p<ni) p++;
                g<<p<<'\n';

            }

        }
    }
}