#include <iostream>
#include <climits>
#include <fstream>
using namespace std;
ifstream f("ssm.in");
ofstream g("ssm.out");

int main()
{
    /*int startmax,maxi,n,v=0,vlast,i,start=1,vmax=INT_MIN;
    f>>n;
    for(i=1;i<=n;i++)
    {
        vlast=v;
        f>>v;
        if(vlast>=0)
            v+=vlast;
        else
            start=i;
        if(v>vmax)
        {
            vmax=v;
            maxi=i;
            startmax=start;
        }
    }
    g<<vmax<<' '<<startmax<<' '<<maxi;
    return 0;*/
    /*int n,v=INT_MIN,i,vlast,x=1,sir[100001],leng;
    f>>n;
    for(i=1;i<=n;i++)
    {
        vlast=v;
        f>>v;
        if(v>vlast)
        {
            c++;
            sir[x]=v;
            x++;
        }
        else if(v<vlast)
        {
            leng=c;
            x=1;
        }
    }
    return 0;*/
    int x,q,v[100002],i,n,s=1,d,mj,r,m;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
        n++;
        v[n]=INT_MAX;
    f>>m;
    for(i=1;i<=m;i++)
    {
        s=1;
        d=n;
        f>>q>>x;
        if(q<2)
        {
            while(s<=d)
            {
                mj=(s+d)/2;
                if(v[mj]>x)
                {
                    r=mj;
                    d=mj-1;
                }
                else
                {
                    s=mj+1;
                }
            }
            if(q==0)
            {
                if(v[r-1]==x)
                    g<<r-1;
                else
                    g<<-1;
            }
            else
                g<<r-1;
        }
        else
        {
            while(s<=d)
            {
                mj=(s+d)/2;
                if(v[mj]>=x)
                {
                    r=mj;
                    d=mj-1;
                }
                else
                {
                    s=mj+1;
                }
            }
            g<<r;
        }
        g<<'\n';
    }
    return 0;
}