from typing import List
from typing import Tuple

def readFromFile(array: List[int], operations: List[Tuple[int]]) -> Tuple[int]:
    with open('cautbin.in', 'r') as fp:
        n, = [int(x) for x in next(fp).split()]
        array.extend([int(x) for x in next(fp).split()])
        m, = [int(x) for x in next(fp).split()]
        for line in fp:
            operations.append(tuple([int(x) for x in line.split()]))
        fp.close()
    return n, m


def printToFile(value: int) -> None:
    global out
    out.write(value.__str__() + '\n')


def binarySearch(array: List[int], value: int, left: int, right: int) -> int:

    global closestPosition

    if left > right:
        closestPosition = left
        return -1

    middle = (left + right) // 2

    if array[middle] == value:
        return middle
    elif array[middle] > value:
        binarySearch(array, value, left, middle - 1)
    else:
        binarySearch(array, value, middle + 1, right)


def solve(n: int, array: List[int], m: int, operations: List[Tuple[int]]) -> None:
    for operation, value in operations:

        if operation == 0:

            position = binarySearch(array, value, 0, n - 1)
            if(position == -1):
                printToFile(-1)
                continue

            while(array[position] == value):
                position += 1
            printToFile(position - 1 + 1)  # + 1 pt ca numerotarea e de la 0

        elif operation == 1:

            position = binarySearch(array, value, 0, n - 1)
            if position == -1:
                printToFile(closestPosition)
                continue

            while(array[position] == value):
                position += 1
            printToFile(position - 1 + 1)

        else:

            position = binarySearch(array, value, 0, n - 1)
            if position == -1:
                printToFile(closestPosition)
                continue

            while(array[position] == value):
                position -= 1
            printToFile(position + 1 + 1)


closestPosition = 0
out = open("cautbin.out", 'w')


def main() -> int:
    array = []
    operations = []
    n = 0
    m = 0
    global out

    n, m = readFromFile(array, operations)
    solve(n, array, m, operations)

    out.close()
    return 0

main()