#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100001],n;

int caut0(int x)
{

    int st,dr,mij,p;
    p=-1; st=1; dr=n;
    while(st<=dr)
    {

        mij=(st+dr)/2;
        if(a[mij]==x)
        {
            p=mij;
            st=mij+1;
        }
        else
        if(x>a[mij])
            st=mij+1;
        else
             dr=mij-1;
    }
    return p;
}
int caut1(int x)
{
    int st,dr,mij,p;
    p=-1; dr=n; st=1;
    while(st<=dr)
    {

        mij=(st+dr)/2;
        if(a[mij]<=x)
        {
            p=mij;
            st=mij+1;
        }
          else dr=mij-1;
        }
        return p;
    }
int caut2(int x)
{

    int st,dr,mij,p;
    p=-1; dr=n; st=1;
    while(st<=dr)
    {

        mij=(st+dr)/2;
        if(a[mij]>=x)
        {
            p=mij;
            dr=mij-1;
        }
        else st=mij+1;
}
return p;
}

int main()
{
    int m,i,x,t;
  f>>n;
  for(i=1;i<=n;i++)
        f>>a[i];
        f>>m;
        for(i=1;i<=m;i++)
        {
            f>>t>>x;
            if(t==0)
            g<<caut0(x)<<endl;
            else
            if(t==1)
            g<<caut1(x)<<endl;
            else g<<caut2(x)<<endl;
    }
}