fi = open("cautbin.in", "r")
fo = open("cautbin.out", "w")

def citeste():
    aux = fi.readline()
    chestie = aux.split()
    chestie = list(map(int, chestie))
    return chestie

def pozPrimulMaiMareEgal(n, sir, val):
    st = 0
    dr = n - 1
    if sir[n - 1] < val:
        return -1
    if sir[st] >= val:
        return 0
    
    while dr - st > 1:
        mij = (st + dr) // 2
        if sir[mij] < val:
            st = mij
        else:
            dr = mij
    
    return dr


n = int(fi.readline())

sir = citeste()


q = int(fi.readline())

#print(pozPrimulMaiMareEgal(n, sir, 3))

for rep in range(0, q):
    op, x = citeste()
    if op == 0: # cea mai mare pozitie pe care am x; daca nu am, -1
        ans = pozPrimulMaiMareEgal(n, sir, x + 1)
        if ans == -1: # nu am >=x+1
            if sir[n - 1] == x:
                fo.write(str(n - 1 + 1) + "\n")
            else:
                fo.write(str(-1) + "\n")
        else:
            if ans == 0:
                fo.write(str(-1) + "\n")
            else:
                fo.write(str(ans - 1 + 1) + "\n")
    elif op == 1: # cea mai mare pozitie pe care am <=x
        ans = pozPrimulMaiMareEgal(n, sir, x + 1)
        if ans == -1:
            fo.write(str(n - 1 + 1) + "\n")
        else:
            fo.write(str(ans - 1 + 1) + "\n")
    elif op == 2: # cea mai mica pozitie pe care am >=x
        ans = pozPrimulMaiMareEgal(n, sir, x)
        fo.write(str(ans + 1) + "\n")