#include <fstream>
#define nmax 100001
#define mid (left+right)/2
using namespace std;
ifstream is ("cautbin.in");
ofstream os ("cautbin.out");

int N, M, A[nmax], type, x;
int BS1(int,int);
int BS2(int,int);
int BS3(int,int);

int main()
{
    is >> N;
    for(int i = 1; i <= N; ++i)
        is >> A[i];
    is >> M;
    for(int i = 1; i <= M; ++i)
    {
        is >> type >> x;
        switch(type){
            case 0:
                os << BS1(1,N) << "\n";
                break;
            case 1:
                os << BS2(1,N) << "\n";
                break;
            case 2:
                os << BS3(1,N) << "\n";
                break;
        }
    }
    is.close();
    os.close();
    return 0;
}
int BS1(int left, int right)
{
    int ANSW = -1;
    while(left <= right)
    {
        if(A[mid] == x)
        {
            ANSW = mid;
            left = mid+1;
        }
        if(A[mid] < x)
            left = mid+1;
        if(A[mid] > x)
            right = mid-1;
    }
    return ANSW;
}
int BS2(int left, int right)
{
    int ANSW = 0;
    while(left <= right)
    {
        if(A[mid] <= x)
        {
            ANSW = mid;
            left = mid+1;
        }
        if(A[mid] > x)
            right = mid-1;
    }
    return ANSW;
}
int BS3(int left, int right)
{
    int ANSW = 0;
    while(left <= right)
    {
        if(A[mid] >= x)
        {
            ANSW = mid;
            right = mid-1;
        }
        if(A[mid] <= x)
            left = mid+1;
    }
    return ANSW;
}