# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
P = IL()

P = [p-1 for p in P]

class SegmentTree:
  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
 
  def get(self, i):
    i += self.size
    ret = self.node[i]
    while i > 1:
      i >>= 1
      ret += self.node[i]
    return ret
 
  def add(self, l, r, val):
    l, r = l + self.size, r + self.size
    while l < r:
      if l & 1:
        self.node[l] += val
        l += 1
      if r & 1:
        r -= 1
        self.node[r] += val
      l, r = l >> 1, r >> 1
      
STA = SegmentTree(N,0)
STB = SegmentTree(N,0)

STA.build(list(range(N)))
STB.build(list(range(N)[::-1]))

prev = P[0]
for p in P[1:]:
  toadd = (STA.get(prev)+STB.get(prev)) - (STA.get(p)+STB.get(p)) + 1
  toadd = max(0,toadd)
  if p>prev:
    STA.add(p,N,toadd)
    if p+1 <= N-1:
      STB.add(p+1,N,-toadd)
  else:
    STB.add(0,p+1,toadd)
    if p >= 1:
      STA.add(0,p,-toadd)
  prev = p
  
ansa = [STA.get(i) for i in range(N)]
ansb = [STB.get(i) for i in range(N)]

mina = min(ansa)
minb = min(ansb)

ansa = [i-mina+1 for i in ansa]
ansb = [i-minb+1 for i in ansb]

print(*ansa)
print(*ansb)
"""
wa = [ansa[i]+ansb[i] for i in range(N)]
wasort = [wa[P[i]] for i in range(N)]
for i in range(N-1):
  if ansa[i] > ansa[i+1]:
    exit()
  if ansb[i] < ansb[i+1]:
    exit()
  if wasort[i] > wasort[i+1]:
    exit()

print(*wasort)
"""


Measured memory_bytes: 74992