#include<fstream>
#define limit 100000
using namespace std;

/******************************************************
 *     Declarations                                   *
 ******************************************************/
/// Variables
int mat[limit];
int n,m;
/// Functions
int q0(int);
int q0lastcheck(int, int);
int q1(int);
int q2(int);

/******************************************************
 *     Main function                                  *
 ******************************************************/
int main()
{
    int quest, x, pos;
    ifstream in ("cautbin.in");
    ofstream out ("cautbin.out");
    in>>n;
    for (int i=0;i<n;i++)
        in>>mat[i];
    in>>m;
    for (int i=0;i<m;i++)
    {   in>>quest>>x;
        if (quest==0) out<<q0(x)<<endl;
        else if (quest==1) out<<q1(x)<<endl;
        else if (quest==2) out<<q2(x)<<endl;
    }

    in.close();
    out.close();
    return 0;
}


/******************************************************
 *  Question type 0                                   *
 *     - Find value                                   *
 ******************************************************/
int q0(int value)
{
    int Left=-1, Right=n, Mid;
    while (Left!=Right-1) {
        Mid=(Left+Right)/2;
        if (mat[Mid]==value) return q0lastcheck(Mid, value);
        else if (mat[Mid]<value) Left=Mid;
        else if (mat[Mid]>value) Right=Mid;
    }
    return -1;
}

int q0lastcheck(int pos, int value)
{
    while (mat[pos]==value) pos++;
    return pos;
}

/******************************************************
 *  Question type 1                                   *
 *      - Find first number smaller or equal to value *
 ******************************************************/
 int q1(int value)
 {
    int Left=-1, Right=n, Mid;

    while (Left!=Right-1) {
        Mid=(Left+Right)/2;
        if (mat[Mid]==value) return Mid+1;
        else if (mat[Mid]<value) Left=Mid;
        else if (mat[Mid]>value) Right=Mid;
    }

    while (mat[Mid]>value && Mid>=0) Mid--;
    while (mat[Mid]<value && Mid<n) Mid++;
    return Mid;
 }

/******************************************************
 *  Question type 2                                   *
 *      - Find first number bigger or equal to value  *
 ******************************************************/

int q2(int value)
{
    int Left=-1, Right=n, Mid;

    while (Left!=Right-1) {
        Mid=(Left+Right)/2;
        if (mat[Mid]==value) return Mid+1;
        else if (mat[Mid]<value) Left=Mid;
        else if (mat[Mid]>value) Right=Mid;
    }

    while (mat[Mid]<value) Mid++;
    while (mat[Mid]>value) Mid--;
    return Mid+2;
}