from math import log2


def cautbin0(nr):
    l2 = int(log2(len(v)))
    p = 1 << l2  # echivalent cu 2^l2
    poz = 0
    while p > 0:
        if poz + p < len(v) and v[poz + p] <= nr:
            poz += p
        p //= 2  # echvialent cu p = p >> 1
    if v[poz] == nr:
        return poz
    else:
        return -2


def cautbin1(nr):
    l2 = int(log2(len(v)))
    p = 1 << l2  # echivalent cu 2^l2
    poz = 0
    while p > 0:
        if poz + p < len(v) and v[poz + p] <= nr:
            poz += p
        p //= 2  # echvialent cu p = p >> 1

    return poz


def cautbin2(nr):
    l2 = int(log2(len(v)))
    p = 1 << l2  # echivalent cu 2^l2
    poz = 0
    while p > 0:
        if poz + p < len(v) and v[poz + p] < nr:
            poz += p
        p //= 2  # echvialent cu p = p >> 1

    return poz + 1


fin = open("cautbin.in")
fout = open("cautbin.out", "w")
fin.readline()
v = [int(i) for i in fin.readline().split()]
fin.readline()
for i in fin:
    test, nr = [int(x) for x in i.split()]
    if test == 0:
        fout.write(str(cautbin0(nr) + 1) + '\n')
    if test == 1:
        fout.write(str(cautbin1(nr) + 1) + '\n')
    if test == 2:
        fout.write(str(cautbin2(nr) + 1) + '\n')

fin.close()
fout.close()