from bisect import bisect_left, bisect_right
with open("date.in", "r") as f, open("date.out", "w") as g:
    n, a, m = int(f.readline()), list(int(i) for i in f.readline().split()), int(f.readline())
    for i in range(m):
        o, x = (int(i) for i in f.readline().split())
        if o == 0:
            poz = bisect_right(a, x)
            g.write(str(poz if poz and a[poz - 1] == x else -1))
        elif o == 1:
            g.write(str(bisect_right(a, x)))
        else:
            g.write(str(bisect_left(a, x) + 1))
        g.write('\n')