There are $n$ people in a row. The height of the $i$-th person is $a_i$. You can choose any subset of these people and try to arrange them into a balanced circle.

A balanced circle is such an order of people that the difference between heights of any adjacent people is no more than $1$. For example, let heights of chosen people be $[a_{i_1}, a_{i_2}, \dots, a_{i_k}]$, where $k$ is the number of people you choose. Then the condition $|a_{i_j} - a_{i_{j + 1}}| \le 1$ should be satisfied for all $j$ from $1$ to $k-1$ and the condition $|a_{i_1} - a_{i_k}| \le 1$ should be also satisfied. $|x|$ means the absolute value of $x$. It is obvious that the circle consisting of one person is balanced.

Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of people.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the height of the $i$-th person.


-----Output-----

In the first line of the output print $k$ — the number of people in the maximum balanced circle.

In the second line print $k$ integers $res_1, res_2, \dots, res_k$, where $res_j$ is the height of the $j$-th person in the maximum balanced circle. The condition $|res_{j} - res_{j + 1}| \le 1$ should be satisfied for all $j$ from $1$ to $k-1$ and the condition $|res_{1} - res_{k}| \le 1$ should be also satisfied.


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

Output
5
2 1 1 2 3

Input
5
3 7 5 1 5

Output
2
5 5 

Input
3
5 1 4

Output
2
4 5 

Input
7
2 2 3 2 1 2 2

Output
7
1 2 2 2 2 3 2

Difficulty: HARD
Tags: Greedy algorithms

Dynamic programming

Amortized analysis

Constructive algorithms
Skill types: Dynamic programming

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def __next__(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = self.next_line()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_line(self, _map=str):
		return list(map(_map, sys.stdin.readline().split()))

	def next_int(self):
		return int(next(self))

	def solve(self):
		n = self.next_int()
		x = sorted([self.next_int() for _ in range(0, n)])
		ml = -1
		_i = 0
		_j = 0
		j = 0
		for i in range(0, n):
			j = max(j, i)
			while j + 1 < n and x[j + 1] == x[i]:
				j += 1
			while j + 2 < n and x[j + 2] == x[j] + 1:
				j += 2
				while j + 1 < n and x[j + 1] == x[j]:
					j += 1
			jj = j
			if j + 1 < n and x[j + 1] == x[j] + 1:
				jj += 1
			if jj - i > ml:
				ml = jj - i
				_i = i
				_j = jj
		a = []
		b = []
		i = _i
		while i <= _j:
			a.append(x[i])
			i += 1
			while i <= _j and x[i] == a[-1]:
				b.append(x[i])
				i += 1
		print(ml + 1)
		print(' '.join([str(x) for x in a + b[::-1]]))

def __starting_point():
	Main().solve()
__starting_point()


import io
import os
from collections import defaultdict
from sys import stdin, stdout

def main():
	n = int(input())
	a = list(map(int, input().split()))
	s = sorted(set(a))
	d = {}
	for val in s:
		d[val] = 0
	for val in a:
		d[val] += 1
	max_len = 1
	res = [a[0]]
	for j in range(len(s) - 1):
		if d[s[j]] == 1 and d[s[j + 1]] == 1 and (s[j + 1] - s[j] == 1):
			max_len = 2
			res = [s[j], s[j + 1]]
			break
	start = 0
	while start < len(s) and d[s[start]] == 1:
		start += 1
	while start < len(s):
		if start < len(s):
			l = start
			r = start
			while l > 0 and d[s[l - 1]] > 1 and (s[l] - s[l - 1] == 1):
				l -= 1
			while r < len(s) - 1 and d[s[r + 1]] > 1 and (s[r + 1] - s[r] == 1):
				r += 1
			if l > 0 and s[l] - s[l - 1] == 1:
				l -= 1
			if r < len(s) - 1 and s[r + 1] - s[r] == 1:
				r += 1
			total = 0
			for j in range(l, r + 1):
				total += d[s[j]]
			if total > max_len:
				max_len = total
				res = []
				for j in range(l, r + 1):
					res.append(s[j])
					d[s[j]] -= 1
				for j in range(r, l - 1, -1):
					while d[s[j]] > 0:
						res.append(s[j])
						d[s[j]] -= 1
			start = r + 1
			while start < len(s) and d[s[start]] == 1:
				start += 1
	print(len(res))
	print(*res)
main()


n = int(input())
a = [int(x) for x in input().split()]
c = [0] * 2 * 100007
s = [0] * 2 * 100007
result = 0
dis = 0
result_list = []
for i in a:
	c[i] += 1
for i in range(len(c)):
	if c[i] > 0:
		s[i] = c[i]
		result = c[i]
		dis = i
		break
for i in range(dis + 1, len(c)):
	if c[i] > 1:
		s[i] = max(s[i - 1] + c[i], c[i - 1] + c[i])
	else:
		s[i] = 0
for i in range(1, len(s)):
	if c[i] + s[i - 1] > result:
		result = c[i] + s[i - 1]
		dis = i
	if c[i] + c[i - 1] > result:
		result = c[i] + c[i - 1]
		dis = i
for i in range(dis - 1, -1, -1):
	if c[i] == 1:
		pos = i
		break
	if c[i] == 0:
		pos = i + 1
		break
print(result)
for i in range(pos, dis + 1):
	print(i, end=' ')
for i in range(dis, pos - 1, -1):
	for j in range(1, c[i]):
		print(i, end=' ')


def unique(a):
	if len(a) == 0:
		return a
	i = 1
	j = 1
	last = a[0]
	while j < len(a):
		if a[j] > last:
			last = a[j]
			(a[i], a[j]) = (a[j], a[i])
			i += 1
		j += 1
	return a[:i]

def expand(cir):
	e = []
	for i in range(len(cir)):
		e.append(cir[i][0])
	for i in range(-1, -len(cir) - 1, -1):
		for _ in range(cir[i][1] - 1):
			e.append(cir[i][0])
	return e
n = int(input())
a = list(map(int, input().split(' ')))
c = dict()
for x in a:
	if x in c:
		c[x] += 1
	else:
		c[x] = 1
a.sort()
a = unique(a)
n = len(a)
cir = []
cirsize = 0
i = 0
while i < n:
	j = i + 1
	while j < n and a[j] == a[j - 1] + 1 and (c[a[j]] > 1):
		j += 1
	if j < n and a[j] == a[j - 1] + 1:
		j += 1
	sz = 0
	for p in range(i, j):
		sz += c[a[p]]
	if sz > cirsize:
		cir.clear()
		for p in range(i, j):
			cir.append((a[p], c[a[p]]))
		cirsize = sz
	if c[a[j - 1]] == 1 and i != j - 1:
		i = j - 1
	else:
		i = j
print(cirsize)
print(*expand(cir))


rint = lambda : int(input())
rmint = lambda : map(int, input().split())
rlist = lambda : list(rmint())
n = rint()
a = [0, 0] * (10 ** 5 + 1)
for c in rlist():
	a[c] += 1
pr = 0
t = 0
ans = 0
g = 0
for i in range(1, 2 * 10 ** 5 + 1):
	if a[i] < 2:
		t = 0
		pr = a[i]
	else:
		t += a[i]
	nx = a[i + 1]
	if pr + t + nx > ans:
		ans = pr + t + nx
		g = i
r = g + 1
l = g + 1
while a[l - 1] > 1:
	l -= 1
while a[r] > 1:
	r += 1
print(ans)

def out(x, y=1):
	while y:
		print(x, end=' ')
		y -= 1
for i in range(l, r):
	out(i)
out(r, a[r])
for i in range(r - 1, l - 1, -1):
	out(i, a[i] - 1)
out(l - 1, a[l - 1])


import sys
from collections import namedtuple
from itertools import groupby
input = sys.stdin.readline

def main():
	Data = namedtuple('Data', ['arr', 'l', 'r'])
	_ = int(input())
	a = list(map(int, input().split()))
	f = [[0, 0] for i in range(max(a) + 2)]
	for x in a:
		f[x][0] = x
		f[x][1] += 1
	best = 0
	opt = None
	for (k, v) in groupby(f, key=lambda x: 1 if x[1] else 0):
		if not k:
			continue
		v = list(v)
		i = lst = len(v) - 1
		t = [0] * (len(v) + 1)
		while i >= 0:
			t[i] = t[i + 1] + v[i][1]
			if t[i] - t[lst + 1] > best:
				best = t[i] - t[lst + 1]
				opt = Data(v, i, lst)
			if v[i][1] == 1:
				lst = i
			i -= 1
	ans = []
	for i in range(opt.l, opt.r + 1):
		ans.append(opt.arr[i][0])
		opt.arr[i][1] -= 1
	for i in range(opt.r, opt.l - 1, -1):
		while opt.arr[i][1]:
			ans.append(opt.arr[i][0])
			opt.arr[i][1] -= 1
	print(len(ans))
	print(' '.join(map(str, ans)))
main()


n = int(input())
a = list(map(int, input().split()))
cnt = [0] * 200005
for i in range(0, n):
	cnt[a[i]] += 1
ans = 0
ansl = 0
ansr = 0
l = 1
N = 200001
while l <= N:
	if cnt[l] == 0:
		l += 1
	else:
		r = l
		now = 0
		while r <= N:
			if cnt[r] == 0:
				r -= 1
				break
			elif cnt[r] == 1 and l != r:
				now += cnt[r]
				break
			else:
				now += cnt[r]
				r += 1
		if now > ans:
			ansl = l
			ansr = r
			ans = now
		if l == r:
			l = r + 1
		else:
			l = r
seq = []
for i in range(ansl, ansr + 1):
	seq.append(i)
	cnt[i] -= 1
for i in range(ansr, ansl - 1, -1):
	while cnt[i] > 0:
		seq.append(i)
		cnt[i] -= 1
print(len(seq))
for i in seq:
	print(i, end=' ')


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
mod = 1000000007

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def YES():
	print('YES')

def NO():
	print('NO')

def Yes():
	print('Yes')

def No():
	print('No')
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

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

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def arr1d(n, v):
	return [v] * n

def arr2d(n, m, v):
	return [[v] * m for _ in range(n)]

def arr3d(n, m, p, v):
	return [[[v] * p for _ in range(m)] for i in range(n)]

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	n = N()
	ar = lis()
	mxn = 200005
	freq = [0] * mxn
	mxcycle = 0
	curcycle = 0
	curans = []
	for i in ar:
		freq[i] += 1
	for i in range(1, mxn):
		if freq[i] > 1:
			curcycle += freq[i]
			curans.append((i, freq[i]))
		else:
			if freq[i] == 1:
				curcycle += freq[i]
				curans.append((i, freq[i]))
			if curcycle > mxcycle:
				mxcycle = curcycle
				mxans = curans.copy()
			curcycle = 0
			curans = [].copy()
	if curcycle > mxcycle:
		mxcycle = curcycle
		mxans = curans.copy()
	if mxcycle == 1:
		for i in range(1, mxn):
			if freq[i] > 0 and freq[i + 1] > 0:
				print(2)
				print(i, i + 1)
				return
	ans = []
	backans = []
	for j in mxans:
		(i, nt) = j
		backans.append(i)
		ans += [i] * (nt - 1)
	ans += backans[::-1]
	if freq[ans[0] - 1] > 0:
		ans = [ans[0] - 1] * freq[ans[0] - 1] + ans
	print(len(ans))
	print(*ans)
solve()


n = int(input())
a = [int(x) for x in input().split()]
if n == 1:
	print(1)
	print(a[0])
	return
a.sort()
b = [a[0]]
cnt = [0] * (200 * 1000 + 1)
cnt[a[0]] += 1
for i in range(1, n):
	cnt[a[i]] += 1
	if a[i - 1] != a[i]:
		b.append(a[i])
l = 0
r = 1
ans = cnt[a[0]]
i = 0
while i < len(b):
	j = i + 1
	su = cnt[b[i]]
	while j < len(b) and b[j] - b[j - 1] == 1 and (cnt[b[j]] >= 2):
		su += cnt[b[j]]
		j += 1
	tmp = j
	if j < len(b) and b[j] - b[j - 1] == 1:
		su += cnt[b[j]]
		j += 1
	if ans < su:
		ans = su
		l = i
		r = j
	i = tmp
print(ans)
for i in range(l, r):
	print(b[i], end=' ')
for i in range(r - 1, l - 1, -1):
	for j in range(0, cnt[b[i]] - 1):
		print(b[i], end=' ')


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
m = 200005
cnt = [0] * m
for i in a:
	cnt[i] += 1
k = 0
lr = [-1, -1]
r = -1
for i in range(m):
	if i < r:
		continue
	if 2 <= cnt[i]:
		(l, r) = (i, i)
		x = 0
		while 2 <= cnt[r]:
			x += cnt[r]
			r += 1
		r -= 1
		x += cnt[l - 1] + cnt[r + 1]
		if cnt[l - 1]:
			l -= 1
		if cnt[r + 1]:
			r += 1
		if k < x:
			k = x
			lr = [l, r]
if k == 0:
	for i in range(m - 1):
		if cnt[i] and cnt[i + 1]:
			k = 2
			lr = [i, i + 1]
			break
	if k == 0:
		k = 1
		lr = [a[0], a[0]]
(l, r) = lr
a = []
for i in range(l, r + 1):
	a.append(i)
	cnt[i] -= 1
for i in range(r, l - 1, -1):
	for _ in range(cnt[i]):
		a.append(i)
print(k)
print(*a)


__version__ = '0.1'
__date__ = '2019-04-26'
import sys

def solve(n, a):
	max_a = max(a)
	counter = [0 for i in range(max_a + 1)]
	for ai in a:
		counter[ai] += 1
	best_group = []
	best_total = 0
	curr = 1
	while curr <= max_a:
		if counter[curr] > 0:
			curr_group = [curr]
			curr_total = counter[curr]
			curr += 1
			if curr > max_a:
				break
			while counter[curr] > 1:
				curr_group.append(curr)
				curr_total += counter[curr]
				curr += 1
				if curr > max_a:
					break
			if curr > max_a:
				break
			if counter[curr] > 0:
				curr_group.append(curr)
				curr_total += counter[curr]
			if curr_total > best_total:
				best_group = curr_group
				best_total = curr_total
		else:
			curr += 1
	if curr_total > best_total:
		best_group = curr_group
		best_total = curr_total
	seq = best_group
	for i in best_group[::-1]:
		seq += [i] * (counter[i] - 1)
	return (best_total, seq)

def main(argv=None):
	n = int(input())
	a = list(map(int, input().split()))
	(total, seq) = solve(n, a)
	print(total)
	print(' '.join(map(str, seq)))
	return 0

def __starting_point():
	STATUS = main()
	return STATUS
__starting_point()


def process(A):
	d = {}
	for x in A:
		if x not in d:
			d[x] = 0
		d[x] += 1
	my_max = [0, None, None]
	current = None
	for x in sorted(d):
		if current is None or x - 1 not in d:
			current = [d[x], x, x]
			my_max = max(my_max, current)
		elif d[x] > 1 and x - 1 in d:
			current[0] += d[x]
			current[2] = x
			my_max = max(my_max, current)
		elif d[x] == 1 and x - 1 in d:
			current[0] += d[x]
			current[2] = x
			my_max = max(my_max, current)
			current = [d[x], x, x]
		else:
			current = None
	if current is not None:
		my_max = max(my_max, current)
	answer_c = my_max[0]
	answer_l = []
	for i in range(my_max[1], my_max[2] + 1):
		answer_l.append(i)
		d[i] -= 1
	for i in range(my_max[2], my_max[1] - 1, -1):
		for j in range(d[i]):
			answer_l.append(i)
	return [answer_c, answer_l]
n = int(input())
A = [int(x) for x in input().split()]
(a1, a2) = process(A)
print(a1)
print(' '.join(map(str, a2)))


kk = lambda : map(int, input().split())
ll = lambda : list(kk())
n = int(input())
d = {}
for v in kk():
	if v not in d:
		d[v] = 0
	d[v] += 1
k = list(d.keys())
k.sort()
i = 0
m = 0
while i < len(k):
	start = x = k[i]
	total = d[start]
	while i + 1 < len(k) and k[i] + 1 == k[i + 1]:
		i += 1
		total += d[k[i]]
		if d[k[i]] == 1:
			if total > m:
				(m, mi) = (total, (start, k[i]))
			break
	else:
		i += 1
		if total > m:
			(m, mi) = (total, (start, k[i - 1]))
print(m)
tbp = []
for i in range(mi[0], mi[1] + 1):
	tbp.extend([i] * (d[i] - 1))
print()
for i in range(mi[1], mi[0] - 1, -1):
	tbp.append(i)
print(*tbp)


import sys
from collections import Counter
input = sys.stdin.readline
n = int(input())
A = Counter(map(int, input().split()))
M = max(A)
DP0 = [0] * (M + 1)
DP1 = [0] * (M + 1)
for i in range(M + 1):
	if A[i] >= 2 and A[i - 1] >= 2:
		DP0[i] = DP0[i - 1] + A[i]
	elif A[i] >= 2 and A[i - 1] == 1:
		DP0[i] = 1 + A[i]
	elif A[i] >= 2 and A[i - 1] == 0:
		DP0[i] = A[i]
	elif A[i] == 1:
		DP0[i] = 1
	if A[i] >= 2:
		DP1[i] = DP0[i]
	elif A[i] == 1:
		DP1[i] = DP0[i - 1] + 1
ANS = max(DP1)
print(ANS)
BIG = DP1.index(ANS)
for i in range(BIG - 1, -1, -1):
	if A[i] == 1:
		SMALL = i
		break
	if A[i] == 0:
		SMALL = i + 1
		break
ANSLIST = list(range(SMALL, BIG + 1))
for i in range(BIG, SMALL - 1, -1):
	for k in range(A[i] - 1):
		ANSLIST.append(i)
print(*ANSLIST)


def solve():
	n = int(input())
	a = sorted(map(int, input().split()))
	ans = (1, 0)
	cur = [a[0]]
	for i in range(1, n):
		if a[i] - a[i - 1] > 1:
			ans = max(ans, (len(cur), i - 1))
			cur.clear()
		elif a[i - 1] < a[i] and (i == n - 1 or a[i] < a[i + 1]):
			cur.append(a[i])
			ans = max(ans, (len(cur), i))
			cur.clear()
		cur.append(a[i])
	ans = max(ans, (len(cur), n - 1))
	print(ans[0])
	ans1 = []
	ans2 = []
	for i in a[ans[1] - ans[0] + 1:ans[1] + 1]:
		if not ans1 or ans1[-1] != i:
			ans1.append(i)
		else:
			ans2.append(i)
	print(*ans1 + ans2[::-1])
for _ in range(1):
	solve()


def create(s, e, cnt):
	arr = []
	for i in range(s, e + 1):
		arr.extend([i for _ in range(cnt[i] - 1)])
	arr.extend(list(range(e, s - 1, -1)))
	return arr
n = int(input())
a = list(map(int, input().split()))

def solve(a):
	cnt = [0] * 200001
	for x in a:
		cnt[x] += 1
	block = []
	max_ = 0
	i = 0
	(s, e) = (None, None)
	while i < len(cnt):
		if cnt[i] > 1:
			s = i
			while i + 1 < len(cnt) and cnt[i + 1] > 1:
				i += 1
			e = i
			if s >= 1 and cnt[s - 1] > 0:
				s -= 1
			if e + 1 < len(cnt) and cnt[e + 1] > 0:
				e += 1
			block.append([s, e])
			i = e + 1
		else:
			i += 1
	pos = -1
	for (i, [s, e]) in enumerate(block):
		sum_ = 0
		for j in range(s, e + 1):
			sum_ += cnt[j]
		if max_ < sum_:
			max_ = sum_
			pos = i
	if max_ >= 2:
		arr = create(block[pos][0], block[pos][1], cnt)
		return (len(arr), ' '.join([str(x) for x in arr]))
	else:
		for i in range(1, 200000):
			if cnt[i] == 1 and cnt[i + 1] == 1:
				return (2, str(i) + ' ' + str(i + 1))
		return (1, str(a[0]))
(length, arr) = solve(a)
print(length)
print(arr)


rint = lambda : int(input())
rmint = lambda : map(int, input().split())
rlist = lambda : list(rmint())
n = rint()
lst = rlist()
cnt = {}
for nb in lst:
	if nb not in cnt:
		cnt[nb] = 1
	else:
		cnt[nb] += 1
arr = sorted(list(cnt.keys()))
N = len(arr)
(left, right, k) = (0, 0, cnt[arr[0]])
(left_best, right_best, k_best) = (0, 0, cnt[arr[0]])
while right < N:
	while right + 1 < N and arr[right + 1] == arr[right] + 1 and (cnt[arr[right]] >= 2):
		right = right + 1
		k += cnt[arr[right]]
	if k_best < k:
		(left_best, right_best, k_best) = (left, right, k)
	if right + 1 >= N:
		break
	elif arr[right + 1] != arr[right] + 1:
		left = right + 1
		right = right + 1
		k = cnt[arr[left]]
	else:
		left = right
		right = right + 1
		k = cnt[arr[left]] + cnt[arr[right]]
print(k_best)
for idx in range(left_best, right_best + 1):
	print((str(arr[idx]) + ' ') * (cnt[arr[idx]] - 1), end='')
for idx in range(right_best, left_best - 1, -1):
	print(str(arr[idx]) + ' ', end='')
print('')