#include<iostream>
#include<cstdlib>
#include<cstdio>
#define lmax 100100
using namespace std;
FILE *f=fopen("cautbin.in","r"),*g=fopen("cautbin.out","w");
int a[lmax],n,m;
int cautbin0(int val)
{
    int inc,sf,m;
    inc=1,sf=n;
    while(inc<=sf)
    {
        m=(inc+sf)/2;
        if(a[m]==val)
        {
            while(a[m]==val)
                m++;
            return (m-1);
        }
        else if(a[m]<val)
            inc=m+1;
        else
            sf=m-1;
    }
    return -1;
}
int cautbin1(int val)
{
    int inc,sf,m;
    inc=1,sf=n;
    while(inc<=sf)
    {
        m=(inc+sf)/2;
        if(a[m]<=val)
        {
            while(a[m]<=val)
                m++;
            return (m-1);
        }
        else
            sf=m-1;
    }
}
int cautbin2(int val)
{
    int inc,sf,m;
    inc=1,sf=n;
    while(inc<=sf)
    {
        m=(inc+sf)/2;
        if(a[m]>=val)
        {
            while(a[m]>=val)
                m--;
            return (m+1);
        }
        else
            inc=m+1;
    }
}
void read()
{
    int i,val;
    short int sw;
    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,"%hd %d",&sw,&val);
        if(sw==0)
            fprintf(g,"%d\n",cautbin0(val));
        else if(sw==1)
            fprintf(g,"%d\n",cautbin1(val));
        else
            fprintf(g,"%d\n",cautbin2(val));
    }
}
int main()
{
    read();
    fclose(f);
    fclose(g);
    return 0;
}