//#include<fstream>
#include<stdio.h>
using namespace std;
long a[100005],n,m,z;

long cautbin0(long x,long st,long dr)
{
    long p=-1,mij;
    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;
}

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

long cautbin2(long x,long st,long dr)
{
    long p=-1,mij;
    p=n+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 ()
{
    //ifstream f("cautbin.in");
    //ofstream g("cautbin.out");
    FILE *f=fopen("cautbin.in","r");
    FILE *g=fopen("cautbin.out","w");
    long x,y,i;
    //f>>n;
    fscanf(f,"%ld",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%ld",&a[i]);
        //f>>a[i];
    }
    //f>>m;
    fscanf(f,"%ld",&m);
    for(i=1;i<=m;i++)
    {
        //f>>y>>x;
        fscanf(f,"%ld %ld",&y,&x);
        if(y==0) z=cautbin0(x,1,n);
        else if(y==1) z=cautbin1(x,1,n);
        else z=cautbin2(x,1,n);
        fprintf(g,"%ld\n",z);
    }
    return 0;
}