#include<stdio.h>

using namespace std;
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()
{
    FILE*f=fopen("cautbin.in","r");
    FILE*g=fopen("cautbin.out","w");
    int m,i,x,t;
  fscanf(f,"%d",&n);
  for(i=1;i<=n;i++)
        fscanf(f,"%d",&a[i]);
        fscanf(f,"%d",&m);
        for(i=1;i<=m;i++)
        {
          fscanf(f,"%d %d",&t,&x);
            if(t==0)
           fprintf(g,"%d\n",caut0(x));
            else
            if(t==1)
           fprintf(g,"%d\n",caut1(x));
            else fprintf(g,"%d\n",caut2(x));
    }
}