#include <fstream>

#define input "cautbin.in"
#define output "cautbin.out"

using namespace std;

ifstream in(input);
ofstream out(output);

int N, arr[100005], queries;

int Task_0(int x)
{
    int sol = -1;
    int st = 1, dr = N;
    while(st <= dr)
    {
        int middle = (st + dr) / 2;
        if(arr[middle] == x){
             sol = middle;
        st = middle + 1;
        }
        else if(arr[middle] > x) dr = middle - 1;
        else st = middle + 1;
    }
    return sol;
}

int Task_1(int x)
{
    int sol = -1;
    int st = 1, dr = N;
    while(st <= dr)
    {
        int middle = (st + dr) / 2;
        if(arr[middle] <= x){
             sol = middle;
        st = middle + 1;
        }
        else if(arr[middle] > x) dr = middle - 1;
        else st = middle + 1;
    }
    return sol;
}

int Task_2(int x)
{
    int sol = -1;
    int st = 1, dr = N;
    while(st <= dr)
    {
        int middle = (st + dr) / 2;
        if(arr[middle] >= x){
             sol = middle;
        dr = middle - 1;
        }
        else if(arr[middle] > x) dr = middle - 1;
        else st = middle + 1;
    }
    return sol;
}

void Read()
{
    in >> N;
    for(int i = 1; i <= N; i++)
        in >> arr[i];
    in >> queries;
    for(int i = 1; i <= queries; i++)
    {
        int task, number;
        in >> task >> number;
        if(task == 0) out << Task_0(number) << "\n";
        if(task == 1) out << Task_1(number) << "\n";
        if(task == 2) out << Task_2(number) << "\n";
    }
}

int main()
{
    Read();
    return 0;
}