//
//  main.cpp
//  018
//
//  Created by adrian ilisei on 30/06/2018.
//  Copyright © 2018 adrian ilisei. All rights reserved.
//

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m;
long v[100010];

int greatestPositionOfNumber(long number, int left, int right)
{
    if(v[right] == number)
        return right;
    if(v[left] == number && v[left + 1] != number)
        return left;
    if(right - left <= 1)
        return -1;
    int half = left + (right - left)/2;
    if(v[half] <= number)
        return greatestPositionOfNumber(number, half, right);
    else
        return greatestPositionOfNumber(number, left, half);
}

int greatestPositionOfLowerOrEqualNumber(long number, int left, int right)
{
    if(v[right] <= number)
        return right;
    if(v[left] <= number && v[left + 1] > number)
        return left;
    int half = left + (right - left)/2;
    if(v[half] <= number)
        return greatestPositionOfLowerOrEqualNumber(number, half, right);
    else
        return greatestPositionOfLowerOrEqualNumber(number, left, half);
}

int lowestPositionOfGreaterOrEqualNumber(long number, int left, int right)
{
    if(v[left] >= number)
        return left;
    if(v[right] >= number && v[right - 1] < number)
        return right;
    int half = left + (right - left)/2;
    if(v[half] >= number)
        return lowestPositionOfGreaterOrEqualNumber(number, left, half);
    else
        return lowestPositionOfGreaterOrEqualNumber(number, half, right);
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>v[i];
    fin>>m;
    int type;
    long number;
    for(int i=1; i<=m; i++)
    {
        fin>>type>>number;
        if(type == 0)
            fout<<greatestPositionOfNumber(number, 1, n)<<"\n";
        if(type == 1)
            fout<<greatestPositionOfLowerOrEqualNumber(number, 1, n)<<"\n";
        if(type == 2)
            fout<<lowestPositionOfGreaterOrEqualNumber(number, 1, n)<<"\n";
    }
    return 0;
}