#include<fstream>
#include<algorithm>

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int n,m,a,k,x,v[100001];

int main ()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a;
        f>>k;
        if(a==0)
        {
            x=upper_bound(v+1,v+n+1,k)-v;
            x--;
            if(v[x]==k)
                g<<x<<"\n";
            else
                g<<"-1\n";
        }
        else if(a==1)
        {
            x=upper_bound(v+1,v+n+1,k)-v;
            x--;
            g<<x<<"\n";
        }
        else if(a==2)
        {
            x=lower_bound(v+1,v+n+1,k)-v;
            g<<x<<"\n";
        }
    }
    f.close();g.close();
    return 0;
}