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]))

aW1wb3J0IHN5cwoKZCA9IGxpc3QobWFwKGludCwgc3lzLnN0ZGluLnJlYWQoKS5zcGxpdCgpKSkKbiwgcCA9IGRbMF0sIGRbMTpdCmggPSBuIC8vIDIKCnNfcG9zID0gW2kgZm9yIGksIHggaW4gZW51bWVyYXRlKHApIGlmIHggPD0gaF0KbF9wb3MgPSBbaSBmb3IgaSwgeCBpbiBlbnVtZXJhdGUocCkgaWYgeCA+IGhdCgppZiBzX3Bvc1stMV0gPCBsX3Bvc1swXSBvciBsX3Bvc1stMV0gPCBzX3Bvc1swXToKICAgIHByaW50KDEpCiAgICBwcmludCgqcCkKICAgIGV4aXQoKQoKcHJpbnQoMikKcHMsIHNsID0gWzBdICogKG4gKyAxKSwgWzBdICogKG4gKyAxKQpmb3IgaSBpbiByYW5nZShuKTogcHNbaSsxXSA9IHBzW2ldICsgKHBbaV0gPD0gaCkKZm9yIGkgaW4gcmFuZ2UobiAtIDEsIC0xLCAtMSk6IHNsW2ldID0gc2xbaSsxXSArIChwW2ldID4gaCkKCmJrLCBiaSA9IG1heCgobWluKHBzW2krMV0sIHNsW2krMV0pLCBpKSBmb3IgaSBpbiByYW5nZShuKSkKCnUsIGMxLCBjMiA9IFtGYWxzZV0gKiBuLCAwLCAwCmZvciBpIGluIHJhbmdlKGJpICsgMSk6CiAgICBpZiBjMSA8IGJrIGFuZCBwW2ldIDw9IGg6IHVbaV0sIGMxID0gVHJ1ZSwgYzEgKyAxCmZvciBpIGluIHJhbmdlKGJpICsgMSwgbik6CiAgICBpZiBjMiA8IGJrIGFuZCBwW2ldID4gaDogdVtpXSwgYzIgPSBUcnVlLCBjMiArIDEKCnByaW50KCoocFtpXSBmb3IgaSBpbiByYW5nZShuKSBpZiB1W2ldKSkKcHJpbnQoKihwW2ldIGZvciBpIGluIHJhbmdlKG4pIGlmIG5vdCB1W2ldKSk=

OAoyIDggNCAzIDEgNSA2IDcg

8
2 8 4 3 1 5 6 7