#include <fstream>
#include <cmath>
using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int n[100000];
int main()
{
    int n1,m,x,y,t,gigel,sa,l=1,k,i,j,h=0,minim=100000,ck,ck1;
    in >>n1;
    for(i=1;i<=n1;i++)
    {
        in >>x;
        n[i]=x;
    }
    k=n1;
    in >>m;
    for(j=1;j<=m;j++)
    {
        in >>y>>t;
        if(y==0)
        {
        while(n[k/2]>t)
        {
            sa=(l+k)/2;
            if(sa>t)
            {
                k=(k-1)/2;
            }
        }
        gigel=k;
        while(gigel)
        {
            gigel--;
            if(n[gigel]==t)
            {
                out <<gigel<<endl;
                h++;
                gigel=0;
            }
        }
        if(h==0)
        {
            out <<"-1"<<endl;
        }
        }
        if(y==1)
        {
            ck=n1;
            while(n[ck/2]>t)
        {
            sa=(l+ck)/2;
            if(sa>t)
            {
                ck=(ck-1)/2;
            }
        }
        gigel=ck;
        while(gigel)
        {
            gigel--;
            if(n[gigel]<=t)
            {
                out <<gigel<<endl;
                gigel=0;
            }
        }
        }
        if(y==2)
        {
            ck1=n1;
            while(n[ck1/2]>t)
        {
            sa=(l+ck1)/2;
            if(sa>t)
            {
                ck=(ck1+1)/2;
            }
        }
        gigel=ck1;
        while(gigel)
        {
            gigel--;
            if(n[gigel]>=t)
            {
                if(minim>gigel)
                {
                    minim=gigel;
                }
            }
        }
        out <<minim<<endl;
        }
    }
    return 0;
}