#include<stdio.h>
int n, v[100001];
int cautareBinara0(int valoare)
{
    int in = 1, sf = n, mij;
    
    while(in < sf)
    {
        mij = in + (sf - in)/2;
        if(valoare >= v[mij]) in = mij + 1;
            else if(valoare < v[mij]) sf = mij - 1;
    }
    
    if(v[in] == valoare)return in;
    else if(v[in-1] == valoare)return in-1;
    return -1;
}
int cautareBinara1(int valoare)
{
    int in = 1, sf = n, mij;
    
    while(in < sf)
    {
        mij = in + (sf - in)/2;
        if(valoare >= v[mij]) in = mij + 1;
        else if(valoare < v[mij]) sf = mij - 1;
    }
    
    if(v[in] <= valoare)return in;
    return in-1;
}
int cautareBinara2(int valoare)
{
    int in = 1, sf = n, mij;
    
    while(in < sf)
    {
        mij = in + (sf - in)/2;
        if(valoare > v[mij]) in = mij + 1;
        else if(valoare <= v[mij]) sf = mij - 1;
    }
    
    if(v[in] <= valoare)return in;
    return in+1;
}
int main()
{
    FILE *inputFile = fopen("cautbin.in", "r"), *outputFile = fopen("cautbin.out", "w");
    
    int i, val, nr, ind;
    
    fscanf(inputFile, "%d", &n);
    for(i = 1; i <= n; i++)
        fscanf(inputFile, "%d", v + i);
    
    fscanf(inputFile,"%d", &nr);
    
    for(i = 1; i <= nr; i++)
    {
        fscanf(inputFile, "%d %d", &ind, &val);
        if(ind == 0) fprintf(outputFile, "%d\n", cautareBinara0(val));
        if(ind == 1) fprintf(outputFile, "%d\n", cautareBinara1(val));
        if(ind == 2) fprintf(outputFile, "%d\n", cautareBinara2(val));
    }
    
    return 0;
}