#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

typedef unsigned int uint;

int binsearch(int *vector, int low, int high, int key);
int floor_value(int *vector, int low, int high, int key);
int ceil_value(int *vector, int low, int high, int key);

int main(void)
{
    FILE *in = fopen("cautbin.in", "r");
    FILE *out = fopen("cautbin.out", "w");
    if(in != NULL && out != NULL)
    {
        int n, i = 0, vector[100005];
        fscanf(in, "%u%*c", &n);
        for(; i < n; i++)
        {
            fscanf(in, "%u%*c", &vector[i]);
        }
        uint q;
        fscanf(in, "%u%*c", &q);
        i = 0;
        for(; i < q; i++)
        {
            uint x, d;
            fscanf(in, "%u%*c%u%*c", &x, &d);
            int res;
            if(x == 0)
            {
                res = binsearch(vector, 0, n, d);
            }
            else if(x == 1)
            {
                res = floor_value(vector, 0, n, d);
            }
            else
            {
                res = ceil_value(vector, 0, n, d);
            }
            if(res != -1)
            {
                fprintf(out, "%d\n", res + 1);
            }
            else
            {
                fprintf(out, "%d\n", -1);
            }
        }

        fclose(in);
        fclose(out);
    }
    else
    {
        printf("Error\n");
    }

    return 0;
}

int ceil_value(int *vector, int low, int high, int key)
{
    while(high - low > 1)
    {
        int mid = low + (high - low) / 2;
        if(vector[mid] >= key)
        {
            high = mid;
        }
        else
        {
            low = mid;
        }
    }
    return (vector[low] >= key) ? low : high;
}

int floor_value(int *vector, int low, int high, int key)
{
    if(key < vector[0])
    {
        return -1;
    }

    while(high - low > 1)
    {
        int mid = low + (high - low) / 2;
        if(vector[mid] <= key)
        {
            low = mid;
        }
        else
        {
            high = mid;
        }
    }
    return low;
}

int binsearch(int *vector, int low, int high, int key)
{
    while(low <= high)
    {
        int mid = low + (high - low) / 2;
        if(vector[mid] == key)
        {
            printf("here %u %u\n", key, mid);
            if(vector[mid + 1] == key)
            {
                while(vector[mid] == key)
                {
                    mid++;
                }
            }
            return mid;
        }
        else if(key > vector[mid])
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}