#include <cstdio>

using namespace std;

int v[100001];
int n;
int cautbin0(int val)
{
    int st=1,dr=n+1;
    while(dr-st>1)
    {
        int mijl=(st+dr)/2;
        if(v[mijl]>val)
            dr=mijl;
        else st=mijl;
    }
    if(val==v[st])
        return st;
    else return -1;
}
int cautbin1(int val)
{
    int st=1,dr=n+1;
    while(dr-st>1)
    {
        int mijl=(st+dr)/2;
        if(v[mijl]>val)
            dr=mijl;
        else st=mijl;
    }
    if(v[dr]<=val&&dr<=n)
    return dr;
    else return st;
}
int cautbin2(int val)
{
    int st=1,dr=n+1;
    while(dr-st>1)
    {
        int mijl=(st+dr)/2;
        if(v[mijl]>=val)
            dr=mijl;
        else st=mijl;
    }
    if(v[st]>=val&&st>=0)
    return st;
    else return dr;
}
int main()
{
    FILE *fin, *fout;
    fin = fopen("cautbin.in", "r");
    fout = fopen("cautbin.out", "w");
    int m;
    fscanf(fin, "%d", &n);
    for(int i=1;i<=n;i++)
        fscanf(fin, "%d", &v[i]);
    fscanf(fin, "%d", &m);
    for(int i=1;i<=m;i++)
    {
        int p,j;
        fscanf(fin, "%d%d", &p,&j);

        if(p==0)
            fprintf(fout, "%d\n", cautbin0(j));
        if(p==1)
           fprintf(fout, "%d\n", cautbin1(j));
        if(p==2)
           fprintf(fout, "%d\n", cautbin2(j));
    }
    return 0;
}