from bio import longestIncreasingSequence as lIS

from bio import longestDecreasingSequence as lDS

fi = open('1.txt')

n = int(fi.readline())

pi = map(int,fi.readline().replace('\n', '').split(' '))

def longestIncreasingSequence(data):

n = len(data)

# q[i] contains the max length of sub seq. ending at array[i]

# p[i] contains predecessor of the sub seq. ending at array[i]

q = [0] * n

p = [-1] * n

for i in range(n):

maxLen = 0

for j in range(i):

if data[i] > data[j]:

if q[j] > maxLen:

maxLen = q[j]

p[i] = j

q[i] = maxLen + 1

idx = q.index(max(q))

seq = []

while (idx != -1):

seq = [data[idx]] + seq

idx = p[idx]

return seq

def longestDecreasingSequence(data):

n = len(data)

# q[i] contains the max length of sub seq. ending at array[i]

# p[i] contains predecessor of the sub seq. ending at array[i]

q = [0] * n

p = [-1] * n

for i in range(n):

maxLen = 0

for j in range(i):

if data[i] < data[j]:

if q[j] > maxLen:

maxLen = q[j]

p[i] = j

q[i] = maxLen + 1

idx = q.index(max(q))

seq = []

while (idx != -1):

seq = [data[idx]] + seq

idx = p[idx]

return seq

print(''.join(str(x)+' ' for x in lIS(pi)))

print(''.join(str(x)+' ' for x in lDS(pi)))