n,*a=map(int,open(0).read().split())
a=[i-1 for i in a]
b,c=[0]*n,[1]*n
l,r=[-1]*n,[-1]*n
g=[[]for _ in range(n)]
for i in range(1,n):
  p=a[0]
  now=a[i]
  for j in range(20):
    if now<p:
      if l[p]==-1:
        l[p]=now
        g[p]+=now,
        b[i]=j+1
        break
      p=l[p]
    else:
      if r[p]==-1:
        r[p]=now
        g[p]+=now,
        b[i]=j+1
        break
      p=r[p]
q=[(a[0],-1,0)]
while q:
  p,z,s=q.pop()
  if s:
    c[z]+=c[p]
    continue
  for v in g[p]:
    if v!=z:
      q+=(v,p,1),(v,p,0),
print(*b)
print(*[c[i]-1for i in a])