def read_gen(fname):
    with open(fname, 'rt') as fin:
        for line in fin:
            for val in line.split():
                yield int(val)
 
def bs_max_pos(x, n, v):
 
    step, pos = 1, 1
    while step <= n: step <<= 1
    while step > 0:
        if pos + step <= n and v[pos + step] <= x:
            pos += step
        step >>= 1
    return -1 if v[pos] != x else pos
 
def bs_max_pos_smaller(x, n, v):
    step, pos = 1, 1
    while step <= n: step <<= 1
    while step > 0:
        if pos + step <= n and v[pos + step] <= x:
            pos += step
        step >>= 1
    return pos
 
def bs_min_pos_bigger(x, n, v):
    step, pos = 1, 1
    while step <= n: step <<= 1
    while step > 0:
        if pos + step <= n and v[pos + step] < x:
            pos += step
        step >>= 1
    return pos + 1
 
if __name__ == "__main__":
    it = read_gen('cautbin.in')
    n = next(it)
    v = [0] + [next(it) for _ in range(n)]
    m = next(it)
    with open('cautbin.out', 'wt') as fout:
        for _ in range(m):
            t, x = next(it), next(it)
            if t == 0:
                pos = bs_max_pos(x, n, v)
            elif t == 1:
                pos = bs_max_pos_smaller(x, n, v)
            elif t == 2:
                pos = bs_min_pos_bigger(x, n, v)
            fout.write('{}\n'.format(pos))