import sys

d = list(map(int, sys.stdin.read().split()))
n, p = d[0], d[1:]
h = n // 2

s_pos = [i for i, x in enumerate(p) if x <= h]
l_pos = [i for i, x in enumerate(p) if x > h]

if s_pos[-1] < l_pos[0] or l_pos[-1] < s_pos[0]:
    print(1)
    print(*p)
    exit()

print(2)
ps, sl = [0] * (n + 1), [0] * (n + 1)
for i in range(n): ps[i+1] = ps[i] + (p[i] <= h)
for i in range(n - 1, -1, -1): sl[i] = sl[i+1] + (p[i] > h)

bk, bi = max((min(ps[i+1], sl[i+1]), i) for i in range(n))

u, c1, c2 = [False] * n, 0, 0
for i in range(bi + 1):
    if c1 < bk and p[i] <= h: u[i], c1 = True, c1 + 1
for i in range(bi + 1, n):
    if c2 < bk and p[i] > h: u[i], c2 = True, c2 + 1

print(*(p[i] for i in range(n) if u[i]))
print(*(p[i] for i in range(n) if not u[i]))