n = int(input())
A = list(map(int, input().split()))
lst = []
id = 0

N = [[] for _ in range(n)]
R = [[] for _ in range(n)]

lst.append([A[0], -1, -1])
id = 1
D = {A[i]: i for i in range(n)}

for i in range(1, n):
    now = 0
    while True:
        a, l, r = lst[now]
        if a < A[i]:
            if r == -1:
                N[D[a]].append(i)
                R[i].append(D[a])
                lst[now][2] = id
                lst.append([A[i], -1, -1])
                id += 1
                break
            else:
                now = r
        else:
            if l == -1:
                N[D[a]].append(i)
                R[i].append(D[a])
                lst[now][1] = id
                lst.append([A[i], -1, -1])
                id += 1
                break
            else:
                now = l

B = [0] * n
C = [1] * n
S = [0]
E = []
while S:
    now = S.pop()
    E.append(now)
    for nxt in N[now]:
        B[nxt] = B[now] + 1
        S.append(nxt)

for e in E[::-1]:
    for nxt in R[e]:
        C[nxt] += C[e]

for i in range(n):
    C[i] -= 1

print(*B)
print(*C)