Sereja loves integer sequences very much. He especially likes stairs.

Sequence a_1, a_2, ..., a_{|}a| (|a| is the length of the sequence) is stairs if there is such index i (1 ≤ i ≤ |a|), that the following condition is met: a_1 < a_2 < ... < a_{i} - 1 < a_{i} > a_{i} + 1 > ... > a_{|}a| - 1 > a_{|}a|.

For example, sequences [1, 2, 3, 2] and [4, 2] are stairs and sequence [3, 1, 2] isn't.

Sereja has m cards with numbers. He wants to put some cards on the table in a row to get a stair sequence. What maximum number of cards can he put on the table?


-----Input-----

The first line contains integer m (1 ≤ m ≤ 10^5) — the number of Sereja's cards. The second line contains m integers b_{i} (1 ≤ b_{i} ≤ 5000) — the numbers on the Sereja's cards.


-----Output-----

In the first line print the number of cards you can put on the table. In the second line print the resulting stairs.


-----Examples-----
Input
5
1 2 3 4 5

Output
5
5 4 3 2 1

Input
6
1 1 2 2 3 3

Output
5
1 2 3 2 1

Difficulty: interview

Starter code:

Solutions:
n=int(input())
a=list(map(int,input().split()))
count=[0]*(10**5+1)
for i in a:
    count[i]+=1
ans=[]
for i in range(10**5+1):
    if count[i]:
        ans.append(i)
        count[i]-=1
if len(ans)!=n:
    for i in reversed(range(10**5+1)):
        if count[i] and ans[-1]!=i:
            ans.append(i)
print(len(ans))
print(*ans)

n = int(input())
quant = [0] * 5001
numbers = list(map(int, input().split()))
res = []
m = max(numbers)

for i in range(n):
    quant[numbers[i]] += 1

i = 1

while i < m:
    if quant[i] > 0:
        res.append(i)
        quant[i] -= 1
    i += 1
res.append(m)
i = m - 1
while i > 0:
    if quant[i] > 0:
        res.append(i)
        quant[i] -= 1
    i -= 1
    
print(len(res))
print(*res)

n = int(input())
a = list(map(int, input().split()))
a.sort()
b=[]
for i in range(n-2):
    if not (a[i] == a[i+1] and a[i] == a[i+2]):
        b.append(a[i])
b.append(a[n-2])
b.append(a[n-1])
if b[-1] == b[-2]:
    b = b[:len(b)-1]
print(len(b))
b1=[]
b2=[]
for i in range(len(b)):
    if i % 2 == 0:
        b2.append(b[i])
    else:
        b1.append(b[i])
for i in b1:
    print(i, end=' ')
b2.reverse()
for i in b2:
    print(i, end=' ')


n = input()
cards = input().split(" ")
cards = [int(cards[i]) for i in range(len(cards))]

if len(cards) == len(list(set(cards))):
    print(n)
    cards.sort()
    for i in range(len(cards) - 1, 0, -1):
        print(cards[i], end=" ")
    print(cards[0], end="\n")
else:
    cards.sort()
    mycards = [cards[0]]

    cards[0] = None
    for i in range(1, len(cards)):
        if cards[i] > mycards[-1]:
            mycards.append(cards[i])
            cards[i] = None

    for i in range(len(cards) - 1, -1, -1):
        if cards[i] == None: continue
        
        if cards[i] < mycards[-1]:
            mycards.append(cards[i])
            cards[i] = None

    print(len(mycards))
    for i in range(len(mycards) - 1):
        print(mycards[i], end=" ")
    print(mycards[-1], end="\n")


import sys
def main():
    l=sys.stdin.readline()
    l=sys.stdin.readline()
    numbers={}
    for el in l.split():
        el=int(el)
        try:
            numbers[el]=numbers[el]+1
        except KeyError:
            numbers[el]=1
        
    nr=numbers.keys()
    nr=sorted(list(set(nr)))
    
    count=0
    final=[]
    for n in nr:
        if numbers[n] > 0:
            final.append(n)
            numbers[n]-=1
            count+=1
    nr=sorted(nr,reverse=True)
    for n in nr:
        if n != final[-1]:
            if numbers[n] > 0:
                final.append(n)
                numbers[n]-=1
                count+=1
    print (count)
    for el in final[:-1]:
        print (el,end = " ")
    print (final[-1])

def __starting_point():
    main()
__starting_point()

__author__ = 'Adela'


def main():

    m = int(input())
    b = [0 for i in range(0, 5001)]
    res = []
    maxi = 0

    for k in input().split():
        nr = int(k)
        b[nr] += 1
        if nr > maxi:
            maxi = nr

    for i in range(0, maxi + 1):
        if b[i] != 0:
            res.append(i)
            b[i] -= 1

    for j in range(maxi - 1, 0, -1):
        if b[j] != 0:
            res.append(j)

    print(len(res))
    for k in res:
        print(k, end=' ')

def __starting_point():
    main()

__starting_point()

n = int(input())
cards = list(map(int, input().split()))
cards.sort()
stair = []
stair_rev = []
stair.append(cards[0])
cards.pop(0)
a = 0
while a < len(cards):
    if cards[a] > stair[-1]:
        stair.append(cards[a])
        cards.pop(a)
    else:
        a+= 1
tmpmax = stair[-1]
cards.sort(reverse = True)
a = 0
while a < len(cards):
    if cards[a] < tmpmax:
        tmpmax = cards[a]
        stair_rev.append(cards[a])
        cards.pop(a)
    else:
        a+= 1
            
stair += stair_rev
print(len(stair))
s = ''
for d in stair[0:-1]:
    s += str(d)+' '
s += str(stair[-1])
print(s)


from collections import Counter
__author__ = 'asmn'

n=int(input())
a=Counter(list(map(int,input().split())))
keys=sorted(a.keys())

for i in range(len(keys)-2,-1,-1):
    if a[keys[i]] > 1:
        keys.append(keys[i])

print(len(keys))
print(' '.join(map(str,keys)))



n = int(input())
test = list(map(int, input().split()))
test1 = []
result = []
test.sort(reverse=True)

num = test.count(test[0])

test1.append(test[0])
mark = 0

for i in range(num, len(test)):
    if test[i] != test1[len(test1)-1]:
        test1.append(test[i])
        mark = 0
    else:
        if mark > 0:
            continue
        else:
            test1.append(test[i])
            mark += 1

result.append(test1[0])
for j in range(1, len(test1)):
    if test1[j] != result[len(result)-1]:
        result.append(test1[j])
    else:
        result.insert(0, test1[j])
print(len(result))
print(' '.join(map(str, result)))


n=int(input())
a=list(map(int,input().split()))
a.sort()
last=0
v=[0]*n
b=[]
for i in range(n):
	if a[i]>last:
		last=a[i]
		b.append(a[i])
		v[i]=1
for i in range(n-1,-1,-1):
	if not v[i] and a[i]<last:
		last=a[i]
		b.append(a[i])
		v[i]=1
print(len(b))
for i in range(len(b)):
	print(b[i],end=' ')


n=int(input())
a=list(map(int,input().split()))
a.sort()
last=0
v=[0]*n
b=[]
for i in range(n):
    if a[i]>last:
        last=a[i]
        b.append(a[i])
        v[i]=1
for i in range(n-1,-1,-1):
    if not v[i] and a[i]<last:
        last=a[i]
        b.append(a[i])
        v[i]=1
tmp=len(b)
print(tmp)
for i in range(tmp):
    print(b[i],end=' ')


input()
a=list(map(int,input().split()))
b=[0]*5000
for x in a:
    b[x-1]+=1
r=''
count=0
max=0
for i in range(5000):
    if b[i]>0:
        count+=1
        max=i
        r+=str(i+1)+' ';
        b[i]-=1
for i in range(max-1,-1,-1):
    if b[i]>0:
        count+=1
        r+=str(i+1)+' ';
print(count)
print(r)

n, t = int(input()), sorted(map(int, input().split()))
a, b, k = [t[0]], [], False
for i in range(1, n):
    if t[i] == t[i - 1]: k = True
    else:
        if k:
            k = False
            b.append(t[i - 1])
        a.append(t[i])
print(len(a) + len(b))
print(' '.join(map(str, a)) + ' ' + ' '.join(map(str, reversed(b))))

n, p = input(), [0] * 5001
for i in map(int, input().split()): p[i] += 1
a = [i for i in range(1, 5001) if p[i]]
b = [i for i in a[: -1] if p[i] > 1]
print(len(a) + len(b))
print(' '.join(map(str, a)) + ' ' + ' '.join(map(str, reversed(b))))

from sys import stdin, stdout

def solve(c, n):
	c = list(sorted(c))
	root = Root()
	root.value = c.pop()
	left_bound = root
	right_bound = root
	while len(c) > 0:
		val = c.pop()
		# print('Current: ' + str(val))
		node = Node()
		node.value = val
		if left_bound.value > val:
			node.prev = left_bound
			if left_bound == root:
				root.left = node
			else:
				left_bound.next = node
			left_bound = node
			# print('appended to left')
		elif right_bound.value > val:
			node.prev = right_bound
			if right_bound == root:
				root.right = node
			else:
				right_bound.next = node
			right_bound = node
		# 	print('appended to right')
		# else:
		# 	print('skipped')
	res_len = 0
	res_str = ''

	p = left_bound
	while p is not root:
		res_str += str(p.value) + ' '
		res_len += 1
		p = p.prev
	res_str += str(p.value) + ' '
	res_len += 1
	p = root.right
	while p is not None:
		res_str += str(p.value) + ' '
		res_len += 1
		p = p.next
	return (res_len, res_str)

class Node:
	value = None
	next = None
	prev = None

class Root:
	value = None
	right = None
	left = None


def __starting_point():
	n_s = stdin.readline()
	cards_s = stdin.readline().split(' ')
	n = int(n_s)
	cards = [int(c) for c in cards_s]
	root = solve(cards, n)
	print('{}\n{}'.format(root[0], root[1]))
__starting_point()

__author__ = 'maaanu'

def start():
    m = int(input())
    cards = [int(x) for x in input().split(" ")]
    cards.sort()
    max_cards = len(cards)
    last_card = cards.pop()
    table = [last_card]

    for val in reversed(cards):
        if val < last_card:
            last_card = val
            table.append(last_card)
        elif val < table[0]:
            table.insert(0, val)
        else:
            max_cards -= 1
    print(max_cards)
    print("".join([str(number)+" " for number in table]))


start()

# -*- coding: utf-8 -*-
import sys

m = int(sys.stdin.readline())
b = [int(x) for x in sys.stdin.readline().split(' ')]

b.sort()

l1 = []
l2 = []

last = b[0]
rep = 1
l1.append(last)
for i in range(1, len(b)):
    if b[i] == last:
        rep += 1
    else:
        last = b[i]
        rep = 1
    if rep == 1:
        l1.append(last)
    elif rep == 2:
        l2.append(last)
    #否则丢弃

if l2 and l2[-1] == l1[-1]:
    l2.pop()
l2.reverse()

print(len(l1)+len(l2))
print(' '.join([str(x) for x in l1]), end='')
if l2:
    print(' ', end='')
    print(' '.join([str(x) for x in l2]))
else:
    print()


import sys
f = sys.stdin
f.readline()
a = sorted([int(x) for x in f.readline().split()])
b = [a[0],]
c = [True]
for i in range(1, len(a)):
    if a[i] != a[i - 1]: b.append(a[i])
    c.append(a[i] != a[i - 1])
for i in range(len(a) - 1, -1, -1):
    if (a[i] < b[-1]) and (not c[i]): b.append(a[i])
print(len(b))
for i in b: print(i, end=' ')



#!/usr/bin/env python3.3
# -*- coding: utf-8 -*-

def sereja_and_stairs ():

    m = input()
    b = input()

    nr_allcards = int(m)
    cards = list(map(int, b.split(' ')))

    nr_cards = [0] * 5001
    max_card = 0
    for card in cards:
        nr_cards[card] += 1
        max_card = max(max_card, card)

    up_stairs = []
    down_stairs = []
    for card in range(1, max_card+1):
        if nr_cards[card] > 0:
            nr_cards[card] -= 1
            down_stairs.append(card)
        if nr_cards[card - 1] > 0:
            up_stairs.append(card - 1)
    down_stairs.reverse()
    stairs = up_stairs + down_stairs

    nr_stairs = len(stairs)
    stairs = ' '.join(map(str,stairs))
    print(('{nr:d}\n{stairs:s}'
          .format(nr=nr_stairs, stairs=stairs)
          ))

    return

def __starting_point():
    sereja_and_stairs()

__starting_point()

#!/usr/bin/env python
# -*- coding: utf-8 -*-


## Python 3 
def sereja_and_stairs ():

    ## 
    # raw_input() → input()
    m = input()
    b = input()

    ## 
    # nr_allcards = int(m)          #
    cards = list(map(int, b.split(' ')))  #

    ##
    nr_cards = [0] * 5001           #
    max_card = 0                    #
    for card in cards:
        nr_cards[card] += 1
        max_card = max(max_card, card)

    ##
    #
    #
    up_stairs = []                  # 
    down_stairs = []                # 
    for card in range(1, max_card+1):
        # 
        if nr_cards[card] > 0:
            nr_cards[card] -= 1
            down_stairs.append(card)
        # 
        if nr_cards[card - 1] > 0:
            up_stairs.append(card - 1)

    ## 
    down_stairs.reverse()
    stairs = up_stairs + down_stairs

    ## 
    # 
    # 
    # [Python2] : print '%d\n%s' % (nr_stairs, stairs)
    # [Python3] : print('{number:d}\n{stairs:s}'.format(number=nr_stairs, stairs=stairs))
    nr_stairs = len(stairs)
    stairs = ' '.join(map(str,stairs))
    print('{number:d}\n{stairs:s}'.format(number=nr_stairs, stairs=stairs))
    return

def __starting_point():
    sereja_and_stairs()

__starting_point()

n = int(input())
s = sorted(map(int, input().split()))
m = 5001
c = [0] * m
for i in range(n):
  c[s[i]] += 1
c[s[-1]] = 1
a = [i for i in range(m) if c[i] > 0] + [i for i in range(m) if c[i] > 1][::-1]
print(len(a))
print(' '.join(map(str, a)))

import sys
import math

n = int(sys.stdin.readline())
an = [int(x) for x in (sys.stdin.readline()).split()]

d = dict()
for i in an:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
        
t = list(d.keys())
t.sort(reverse = True)

resr = []
resl = []
c = 1
resr.append(str(t[0]))
for i in t[1:]:
    if(d[i] > 1):
        c += 2
        resr.append(str(i))
        resl.append(str(i))
    else:
        c += 1
        resr.append(str(i))
        
k = list(resl[::-1])
k.extend(resr)     
print(c)  
print(" ".join(k))

from collections import Counter
n = int(input())
l = Counter(int(x) for x in input().split())
a = []
b = []
for x, y in list(l.items()):
	a.append(x)
	if y > 1:
		b.append(x)
a.sort()
b.sort()
if len(b) and a[-1] == b[-1]:
	b = b[:-1]
ans = a + b[::-1]
print(len(ans))
print(' '.join(str(x) for x in ans))


from itertools import chain


def main():
    input()
    lb, la = [], []
    a = b = -1
    it = iter(sorted(map(int, input().split())))
    try:
        while True:
            c = next(it)
            if a != c:
                a = c
                la.append(a)
            c = next(it)
            if b != c:
                b = c
                lb.append(b)
            pass
    except StopIteration:
        if a == b:
            del lb[-1]
    print(len(la) + len(lb))
    print(' '.join(map(str, chain(la, lb[::-1]))))


def __starting_point():
    main()
__starting_point()