This is the hard version of the problem. The difference between the versions is that in the easy version all prices $a_i$ are different. You can make hacks if and only if you solved both versions of the problem.

Today is Sage's birthday, and she will go shopping to buy ice spheres. All $n$ ice spheres are placed in a row and they are numbered from $1$ to $n$ from left to right. Each ice sphere has a positive integer price. In this version, some prices can be equal.

An ice sphere is cheap if it costs strictly less than two neighboring ice spheres: the nearest to the left and the nearest to the right. The leftmost and the rightmost ice spheres are not cheap. Sage will choose all cheap ice spheres and then buy only them.

You can visit the shop before Sage and reorder the ice spheres as you wish. Find out the maximum number of ice spheres that Sage can buy, and show how the ice spheres should be reordered.


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 10^5)$ — the number of ice spheres in the shop.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$ — the prices of ice spheres.


-----Output-----

In the first line print the maximum number of ice spheres that Sage can buy.

In the second line print the prices of ice spheres in the optimal order. If there are several correct answers, you can print any of them.


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

Output
3
3 1 4 2 4 2 5 


-----Note-----

In the sample it's not possible to place the ice spheres in any order so that Sage would buy $4$ of them. If the spheres are placed in the order $(3, 1, 4, 2, 4, 2, 5)$, then Sage will buy one sphere for $1$ and two spheres for $2$ each.

Difficulty: MEDIUM
Tags: Constructive algorithms

Sorting

Amortized analysis

Greedy algorithms

Complete search
Skill types: Complete search

Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
n = int(input())
arr = list(map(int, input().split()))
flag = 1
if n <= 2:
	print(0)
	print(*arr)
	flag = 0
arr.sort(reverse=True)
final = ['0']
pair = 0
if flag == 1:
	k = 0
	j = 1
	if n % 2 != 0:
		temp1 = arr[:n // 2 + 1]
		temp2 = arr[n // 2 + 1:]
	else:
		temp1 = arr[:n // 2]
		temp2 = arr[n // 2:]
		rem_val = temp2.pop(0)
	for i in range(0, len(temp2)):
		if temp1[k] == temp2[i] or temp1[j] == temp2[i]:
			pass
		else:
			pair += 1
		final.pop(-1)
		final.append(temp1[k])
		final.append(temp2[i])
		final.append(temp1[j])
		k += 1
		j += 1
	if n % 2 == 0:
		final.append(rem_val)
if flag == 1:
	print(pair)
	print(*final)


n = int(input())
ar = list(map(int, input().split()))
ar = sorted(ar)
ans = [0] * n
j = 0
for i in range(1, n, 2):
	ans[i] = ar[j]
	j += 1
j = n // 2
for i in range(0, n, 2):
	ans[i] = ar[j]
	j += 1
cnt = 0
for i in range(1, n - 1):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		cnt += 1
print(cnt)
print(*ans)


n = int(input())
F = [int(i) for i in input().split()]
F.sort()
if n % 2 != 0:
	A = F[:int((n - 1) / 2)]
	B = F[int((n - 1) / 2):]
	for i in range(int((n + 1) / 2)):
		F[2 * i] = B[i]
	for i in range(int((n - 1) / 2)):
		F[2 * i + 1] = A[i]
else:
	A1 = F[:int(n / 2)]
	B1 = F[int(n / 2):]
	for i in range(int(n / 2)):
		F[2 * i] = B1[i]
	for i in range(int(n / 2)):
		F[2 * i + 1] = A1[i]
count = 0
for i in range(1, n - 1):
	if F[i] < F[i - 1] and F[i] < F[i + 1]:
		count += 1
print(count)
print(*F)


from sys import stdin, stdout
import math
t = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
arr.sort()
k = 0
res = []
count = 0
if t % 2 != 0:
	k = (t + 1) // 2
	i = 0
	while i < k - 1:
		if arr[i] < arr[i + k - 1]:
			count += 1
		if i == 0:
			res.append(arr[i + k - 1])
		res.append(arr[i])
		res.append(arr[i + k])
		i += 1
else:
	k = t // 2
	i = 0
	while i < k - 1:
		if arr[i] < arr[i + k - 1] or (i == k - 2 and arr[i] < arr[i + k]):
			count += 1
		if arr[i] >= arr[i + k - 1] and (i == k - 2 and arr[i] < arr[i + k]):
			if i == 0:
				res.append(arr[i + k - 1])
			res.append(arr[i + k])
			res.append(arr[i])
			res.append(arr[i + k + 1])
		else:
			if i == 0:
				res.append(arr[i + k - 1])
			res.append(arr[i])
			res.append(arr[i + k])
			if i == k - 2:
				res.append(arr[i + k + 1])
		i += 1
print(count)
if count == 0:
	print(' '.join((str(i) for i in arr)))
else:
	print(' '.join((str(i) for i in res)))


n = int(input())
array = list(map(int, input().split()))
array.sort()
output = []
array1 = array[0:n // 2]
array2 = array[n // 2:]
i = 0
j = 0
count = 0
while i < n // 2 and j < (n - 1) // 2:
	b = array2[j]
	a = array1[i]
	output.append(b)
	output.append(a)
	if b > a:
		count += 1
	i += 1
	j += 1
if n % 2 != 0:
	output.append(array2[-1])
else:
	output.append(array2[-1])
	output.append(array1[-1])
print(count)
print(' '.join(map(str, output)))


def f():
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	newarr = []
	for i in range(n // 2):
		newarr.append(arr[i + n // 2])
		newarr.append(arr[i])
	if n % 2:
		newarr.append(arr[n - 1])
	total = 0
	i = 1
	while i + 1 < n:
		if newarr[i - 1] > newarr[i] and newarr[i] < newarr[i + 1]:
			total += 1
		i += 2
	newarr = list(map(str, newarr))
	newarr = ' '.join(newarr)
	print(total)
	print(newarr)
f()


n = int(input())
a = sorted(list(map(int, input().split())))
val = 0
(b, c) = (a[:n // 2], a[n // 2:-1])
sol = [a[-1]]
d = []
(b_ptr, c_ptr) = (len(b) - 1, len(c) - 1)
while True:
	if b_ptr < 0 or c_ptr < 0:
		break
	cc = c[c_ptr]
	while b_ptr >= 0:
		if b[b_ptr] >= cc:
			d.append(b[b_ptr])
			b_ptr -= 1
		else:
			break
	if b_ptr < 0:
		break
	else:
		sol.append(b[b_ptr])
		b_ptr -= 1
		sol.append(c[c_ptr])
		c_ptr -= 1
		val += 1
sol += b[:max(b_ptr + 1, 0)] + c[:max(c_ptr + 1, 0)] + d
print(val)
print(' '.join([str(i) for i in sol]))


n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0] * n
k = 0
for j in range(1, n, 2):
	b[j] = a[k]
	k = k + 1
for j in range(0, n, 2):
	b[j] = a[k]
	k = k + 1
m = 0
for j in range(1, n - 1, 2):
	if b[j] != b[j - 1] and b[j] != b[j + 1]:
		m = m + 1
print(m)
print(' '.join(map(str, b)))


n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = [0 for _ in range(n)]
t = n - 1
x = 0
if n % 2 == 0:
	x = 1
for i in range(n - 1 - x, -1, -2):
	ans[i] = l[t]
	t -= 1
t = 0
for i in range(1, n, 2):
	ans[i] = l[t]
	t += 1
t = 0
for i in range(1, n - 1):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		t += 1
print(t)
print(*ans)


import itertools
import math
import sys
from collections import defaultdict

def stdinWrapper():
	data = '7\n1 1 1 1 2 2 2 2 1 \n\n\n'
	for line in data.split('\n'):
		yield line
if '--debug' not in sys.argv:

	def stdinWrapper():
		while True:
			yield input()
inputs = stdinWrapper()

def inputWrapper():
	return next(inputs)

def getType(_type):
	return _type(inputWrapper())

def getArray(_type):
	return [_type(x) for x in inputWrapper().split()]

def solve(a):
	a = sorted(a)
	start = len(a) // 2
	total = 0
	result = [-1 for _ in range(len(a))]
	pos = 0
	while pos < len(a):
		result[pos] = a[start + pos // 2]
		pos += 1
		if pos >= len(a):
			break
		result[pos] = a[pos // 2]
		if pos != len(a) - 1:
			total += 1 if result[pos] < result[pos - 1] else 0
		pos += 1
	return (total, result)
n = getType(int)
a = getArray(int)
(total, result) = solve(a)
print(total)
print(' '.join([str(x) for x in result]))


n = int(input())
a = list(map(int, input().split()))
a.sort()
mi = a[:n // 2]
ma = a[n // 2:]
l = []
for i in range(n):
	if i % 2 == 0:
		l.append(ma[i // 2])
	else:
		l.append(mi[i // 2])
ans = 0
for i in range(1, n - 1):
	if l[i - 1] > l[i] < l[i + 1]:
		ans += 1
print(ans)
print(*l)


def reOrder(arr):
	resArray = []
	arr = sorted(arr)
	mid = len(arr) // 2
	i = 0
	j = mid
	while i < mid and j < len(arr):
		resArray.append(arr[j])
		resArray.append(arr[i])
		i += 1
		j += 1
	while j < len(arr):
		resArray.append(arr[j])
		j += 1
	return resArray

def countPeaks(arr):
	if len(arr) <= 2:
		return 0
	res = 0
	i = 0
	j = i + 2
	while j < len(arr):
		left = arr[i]
		right = arr[j]
		middle = arr[i + 1]
		if middle < left and middle < right:
			res += 1
		i += 1
		j += 1
	return res
n = int(input())
arr = list(map(int, input().split()))
resArray = reOrder(arr)
res = countPeaks(resArray)
print(res)
print(*resArray)


n = int(input())
mas = list(map(int, input().split()))
mas = sorted(mas)
middle = n // 2
masans = []
ans = 0
if n > 1:
	for i in range(n // 2):
		if mas[i] < mas[i + middle]:
			ans += 1
		masans.append(mas[i + middle])
		masans.append(mas[i])
	if n % 2 != 0:
		masans.append(mas[n - 1])
	if n % 2 == 0:
		if masans[-1] < masans[-2]:
			ans -= 1
else:
	ans = 0
	masans = [mas[0]]
print(ans)
for x in masans:
	print(x, end=' ')


from collections import defaultdict

def main():
	n = int(input())
	d = defaultdict(int)
	l = list(map(int, input().split()))
	l.sort()
	count = 0
	k = []
	for i in range(n // 2 - 1, -1, -1):
		k.append(l[i + (n + 1) // 2])
		k.append(l[i])
	if n % 2:
		k.append(l[n // 2])
	if n > 2:
		for i in range(1, n):
			if k[i] == k[i - 1]:
				k = k[:i - 1] + [k[i - 1], k[-1]] + k[i:-1]
				break
		for i in range(1, n - 1):
			if k[i] < k[i - 1] and k[i] < k[i + 1]:
				count += 1
	print(count)
	print(' '.join(map(str, k)))

def SumOfExpOfFactors(a):
	fac = 0
	lis = SortedList()
	if not a & 1:
		lis.add(2)
	while not a & 1:
		a >>= 1
		fac += 1
	for i in range(3, int(a ** 0.5) + 1, 2):
		if not a % i:
			lis.add(i)
		while not a % i:
			a //= i
			fac += 1
	if a != 1:
		lis.add(a)
		fac += 1
	return (fac, lis)
div = [0] * 1000001

def NumOfDivisors(n):
	for i in range(1, n + 1):
		for j in range(i, n + 1, i):
			div[j] += 1

def primes1(n):
	sieve = [True] * (n // 2)
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i // 2]:
			sieve[i * i // 2::i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]

def GCD(a, b):
	if b == 0:
		return a
	else:
		return GCD(b, a % b)

class Graph:

	def __init__(self):
		self.Graph = defaultdict(list)

	def addEdge(self, u, v):
		self.Graph[u].append(v)
		self.Graph[v].append(u)

	def DFSUtil(self, v, visited):
		visited.add(v)
		for neighbour in self.Graph[v]:
			if neighbour not in visited:
				self.DFSUtil(neighbour, visited)

	def DFS(self, v):
		visited = set()
		self.DFSUtil(v, visited)

	def BFS(self, s):
		visited = set()
		queue = []
		queue.append(s)
		visited.add(s)
		while queue:
			s = queue.pop(0)
			for i in self.Graph[s]:
				if i not in visited:
					queue.append(i)
					visited.add(i)

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))
main()


n = int(input())
l = list(map(int, input().split()))
l.sort()
j = 0
mid = len(l) // 2
a = [0] * (n + 2)
for i in range(mid):
	(a[i + j], a[i + 1 + j]) = (l[mid + i], l[i])
	j += 1
if n % 2 != 0:
	a[n - 1] = l[n - 1]
p = 0
for i in range(1, n):
	if a[i - 1] > a[i] and a[i] < a[i + 1]:
		p += 1
print(p)
a = a[:n]
s = ' '.join(map(str, a))
print(s)


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = [int(X) for X in input().split()]
	a.sort()
	x = a[:n // 2]
	y = a[n // 2:]
	ma = []
	for i in range(len(x)):
		ma.append(y[i])
		ma.append(x[i])
	if n % 2 == 1:
		ma.append(y[-1])
	c = 0
	for i in range(1, n - 1):
		if ma[i] < ma[i - 1] and ma[i] < ma[i + 1]:
			c += 1
	print(c)
	print(*ma)
BUFSIZE = 8192

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input(''))
arr = list(map(int, input().split()))
arr.sort()
i = 0
sol = [0] * n
for j in range(1, n, 2):
	sol[j] = arr[i]
	i += 1
for j in range(0, n, 2):
	sol[j] = arr[i]
	i += 1
cnt = 0
for j in range(1, n - 1):
	if sol[j] < sol[j - 1] and sol[j] < sol[j + 1]:
		cnt += 1
print(cnt)
print(*sol)


import sys
from copy import *
from bisect import *

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def bo(i):
	return ord(i) - ord('A')

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j):
	return 0 <= i < n and 0 <= j < m and (a[i][j] != '.')

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
while t > 0:
	t -= 1
	n = fi()
	a = li()
	a.sort(reverse=True)
	ans = [0] * n
	a = a[:(n + 2) // 2] + sorted(a[(n + 2) // 2:])
	l = c = 0
	r = n - 1
	for i in range(n):
		if i % 2:
			ans[i] = a[r]
			r -= 1
		else:
			ans[i] = a[l]
			l += 1
	for i in range(1, n - 1):
		if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
			c += 1
	print(c)
	print(*ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
g = []
h = []
for j in range(n // 2):
	g.append(a[j])
for j in range(n // 2, n):
	h.append(a[j])
gx = len(g)
hx = len(h)
gy = 0
hy = 0
c = 0
k = []
while gy < gx or hy < hx:
	if gy < gx and hy < hx:
		if g[gy] < h[hy]:
			k.append(h[hy])
			k.append(g[gy])
			hy = hy + 1
			gy = gy + 1
			if hy < hx:
				c = c + 1
		elif g[gy] == h[hy]:
			k.append(h[hy])
			hy = hy + 1
	elif gy == gx:
		k.append(h[hy])
		hy = hy + 1
	else:
		k.append(g[gy])
		gy = gy + 1
print(c)
print(' '.join(map(str, k)))


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, nums):
	nums.sort()
	mid = len(nums) // 2
	ret = []
	if len(nums) % 2 == 1:
		for (x, y) in zip(nums[:mid], nums[mid:-1]):
			ret.append(y)
			ret.append(x)
		ret.append(nums[-1])
	else:
		for (x, y) in zip(nums[:mid], nums[mid:]):
			ret.append(y)
			ret.append(x)
	count = 0
	for i in range(1, N - 1):
		if ret[i - 1] > ret[i] and ret[i] < ret[i + 1]:
			count += 1
	if DEBUG:
		assert set(nums) == set(ret)
	return str(count) + '\n' + ' '.join(map(str, ret))
DEBUG = False
if DEBUG:
	import random
	from itertools import permutations
	random.seed(0)
	for _ in range(100000):
		N = random.randint(1, 7)
		A = [random.randint(1, 10) for i in range(N)]
		print('tc', _, N, A)
		ans1 = solve(N, A)
		brute = 0
		for ret in permutations(A):
			count = 0
			for i in range(1, N - 1):
				if ret[i - 1] > ret[i] and ret[i] < ret[i + 1]:
					count += 1
			brute = max(brute, count)
		ansInt = int(ans1.split('\n')[0])
		print('brute', brute, 'mine', ans1)
		assert brute == ansInt
		print(ans1)
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = solve(N, A)
print(ans)


n = int(input())
arr = [int(x) for x in input().split()]
arr.sort()
(arr[0::2], arr[1::2]) = (arr[n // 2:], arr[:n // 2])
ans = 0
for i in range(1, n - 1):
	if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
		ans += 1
print(ans)
print(*arr)


n = int(input())
a = [int(x) for x in input().split()]
asort = sorted(a)
j = 0
ans = [0] * len(a)
for i in range(1, len(a), 2):
	ans[i] = asort[j]
	j += 1
for k in range(0, len(a), 2):
	ans[k] = asort[j]
	j += 1
total = 0
for num in range(1, len(ans) - 1, 2):
	if ans[num] < ans[num - 1] and ans[num] < ans[num + 1]:
		total += 1
print(total)
print(*ans)


t = int(input())
ice = list(map(int, input().split()))
new_ice = []
count = 0
ice.sort()
if len(ice) % 2 != 0:
	for i in range(0, len(ice) // 2 + 1):
		new_ice.append(ice[len(ice) // 2 + i])
		new_ice.append(ice[i])
	del new_ice[-1]
elif len(ice) <= 2:
	for i in range(len(ice)):
		new_ice.append(ice[i])
else:
	for i in range(0, len(ice) // 2):
		new_ice.append(ice[len(ice) // 2 + i])
		new_ice.append(ice[i])
for i in range(1, len(new_ice) - 1, 1):
	if new_ice[i] < new_ice[i - 1] and new_ice[i] < new_ice[i + 1]:
		count += 1
print(count)
print(' '.join(map(str, new_ice)))


n = int(input())
A = list(map(int, input().split()))
A = sorted(A)
B = A[0:n // 2]
C = A[n // 2:]
a = []
for i in range(len(B)):
	a.append(C[i])
	a.append(B[i])
if n % 2 != 0:
	a.append(C[-1])
ans = 0
for i in range(1, n - 1):
	if a[i] < a[i - 1] and a[i] < a[i + 1]:
		ans += 1
print(ans)
for x in a:
	print(x, end=' ')
print()


import sys
input = sys.stdin.readline
n = int(input())
A = sorted(map(int, input().split()))
ans = [0] * n
j = n - 1
for i in range(0, n, 2):
	ans[i] = A[j]
	j -= 1
rem = []
cnt = 0
pre = -1
for i in range(1, n - 1, 2):
	if j < 0:
		break
	while j >= 0 and A[j] >= ans[i + 1]:
		rem.append(A[j])
		j -= 1
	cnt += 1
	ans[i] = A[j]
	pre = i
	j -= 1
rem += A[:j + 1]
j = 0
if rem:
	for k in range(pre + 2, n, 2):
		ans[k] = rem[j]
		j += 1
print(cnt)
print(*ans)


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = sorted(map(int, input().split()), reverse=1)
	b = [a[0]]
	cnt = 0
	(i, j) = (1, (n - 1) // 2 + 1)
	mark = [0] * n
	mark[0] = 1
	while i != n and j != n:
		while j != n and a[j] == a[i]:
			j += 1
		if j == n:
			break
		mark[j] = 1
		mark[i] = 1
		b.extend([a[j], a[i]])
		while i != n and mark[i]:
			i += 1
		j += 1
	for (ind, val) in enumerate(mark):
		if not val:
			b.append(a[ind])
	for i in range(1, n - 1):
		if b[i - 1] > b[i] and b[i + 1] > b[i]:
			cnt += 1
	print(cnt)
	print(' '.join(map(str, b)))
BUFSIZE = 8192

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
ans = [0] * n
for i in range(1, n, 2):
	ans[i] = l.pop()
for i in range(0, n, 2):
	ans[i] = l.pop()
count = 0
for i in range(1, n - 1):
	if ans[i - 1] > ans[i] and ans[i] < ans[i + 1]:
		count += 1
print(count)
print(*ans)


def solve():
	n = int(input())
	p = list(map(int, input().split()))
	if n <= 2:
		print(0)
		print(*p)
		return
	p.sort()
	a = [0] * n
	l = 0
	k = n
	if n % 2 == 0:
		k -= 1
	for i in range(1, k, 2):
		a[i] = p[l]
		l += 1
	l = n - 1
	for i in range(k - 1, -1, -2):
		a[i] = p[l]
		l -= 1
	if n % 2 == 0:
		a[-1] = p[l]
	cnt = 0
	for i in range(1, n - 1):
		if a[i] < a[i - 1] and a[i] < a[i + 1]:
			cnt += 1
	print(cnt)
	print(*a)
	return

def main():
	t = 1
	for _ in range(t):
		solve()
main()


n = int(input())
spheres = list(map(int, input().split(' ')))
spheres = sorted(spheres)
ret = [-1 for _ in range(n)]
(l, r) = (0, n - 1)
cnt = 0
block_n = n // 2 + n % 2
inner_n = n - block_n
inners = spheres[:inner_n]
blocks = spheres[inner_n:n]
st = 0
if n % 2 == 0:
	ret[0] = inners.pop()
	st = 1
for i in range(st, n):
	if i % 2 == st:
		ret[i] = blocks.pop()
	else:
		ret[i] = inners.pop()
	if i > 1 and ret[i - 1] < ret[i - 2] and (ret[i - 1] < ret[i]):
		cnt += 1
print(cnt)
print(' '.join(list(map(str, ret))))


import sys, os.path
from collections import *
from copy import *
import math
mod = 10 ** 9 + 7
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = int(input())
arr = list(map(int, input().split()))
res = [0] * n
arr.sort()
j = 1
for i in range(n // 2):
	res[j] = arr[i]
	j += 2
j = 0
for i in range(n // 2, n):
	res[j] = arr[i]
	j += 2
x = 0
for i in range(1, n - 1):
	x += res[i - 1] > res[i] < res[i + 1]
print(x)
print(*res)


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = [-1] * n
j = 0
for i in range(0, n, 2):
	ans[i] = a[j]
	j += 1
ansl = 0
check = False
for i in range(1, n, 2):
	ans[i] = a[j]
	if i < n - 1 and ans[i - 1] > ans[i] < ans[i + 1]:
		ansl += 1
	elif i == n - 1:
		check = True
	j += 1
if check:
	for i in range(1, n - 1, 2):
		if not ans[i - 1] > ans[i] < ans[i + 1] and ans[i - 1] > ans[-1] < ans[i + 1]:
			ansl += 1
			(ans[i], ans[-1]) = (ans[-1], ans[i])
			break
print(ansl)
print(*ans)


n = int(input())
arr = [int(num) for num in input().split()]
arr.sort()
arr0 = arr[:n // 2]
arr1 = arr[n // 2:]
p0 = 0
p1 = 0
ans = []
while p0 < len(arr0) and p1 < len(arr1):
	ans.append(arr1[p1])
	ans.append(arr0[p0])
	p0 += 1
	p1 += 1
if n % 2:
	ans.append(arr1[-1])
ans_num = 0
for ind in range(1, n - 1):
	if ans[ind - 1] > ans[ind] < ans[ind + 1]:
		ans_num += 1
print(ans_num)
print(*ans)


n = int(input())
lst = list(map(int, input().split()))
lst.sort()
result = lst[n // 2:]
for i in range(n // 2):
	result.insert(2 * i + 1, lst[i])
cnt = 0
for i in range(1, n - 1):
	if result[i - 1] > result[i] and result[i] < result[i + 1]:
		cnt += 1
print(cnt)
print(' '.join(map(str, result)))


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	a = arr.copy()
	a.sort(reverse=True)
	ind = 0
	for i in range(0, n, 2):
		arr[i] = a[ind]
		ind += 1
	for i in range(1, n, 2):
		arr[i] = a[ind]
		ind += 1
	cnt = 0
	nahi = -1
	ind = -1
	for i in range(n):
		if i != 0 and i != n - 1 and i % 2:
			if arr[i] < arr[i + 1] and arr[i] < arr[i - 1]:
				cnt += 1
			elif nahi == -1:
				nahi = arr[i]
				ind = i
	if n % 2 == 0 and nahi != -1 and (arr[ind] != arr[-1]):
		(arr[-1], arr[ind]) = (arr[ind], arr[-1])
		cnt += 1
	print(cnt)
	print(*arr)
BUFSIZE = 8192

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(1):
	main()


from collections import *
n = int(input())
L = sorted(map(int, input().split()))
lo = range(int(n / 2), 0, -1)
hi = range(n, int(n / 2), -1)
(ans, ans2) = ([], [])
for (a, b) in list(zip(hi, lo)):
	ans.append(L[a - 1])
	ans.append(L[b - 1])
	ans2.append(L[b - 1])
	ans2.append(L[a - 1])
if len(hi) > len(lo):
	ans.append(L[hi[-1] - 1])
	ans2.append(L[hi[-1] - 1])
x = len([x for (i, x) in enumerate(ans) if i > 0 and i < len(ans) - 1 and (ans[i - 1] > ans[i]) and (ans[i + 1] > ans[i])])
y = len([x for (i, x) in enumerate(ans2) if i > 0 and i < len(ans2) - 1 and (ans2[i - 1] > ans2[i]) and (ans2[i + 1] > ans2[i])])
if x > y:
	print(x)
	print(' '.join(map(str, ans)))
else:
	print(y)
	print(' '.join(map(str, ans2)))


import sys
try:
	sys.stdin = open('input.txt', 'r')
except FileNotFoundError:
	pass

def next_array():
	return [int(i) for i in input().split()]

def prefix(lst):
	assert len(lst)
	pre = [lst[0]]
	for i in range(1, len(lst)):
		pre.append(lst[i] + pre[i - 1])
	return pre

def prefix_max(lst):
	assert len(lst)
	pre = [lst[0]]
	for i in range(1, len(lst)):
		pre.append(max(lst[i], pre[i - 1]))
	return pre

def solve():
	n = int(input())
	lst = next_array()
	lst.sort()
	out = [None] * len(lst)
	for i in range(len(lst) // 2, len(lst)):
		out[(i - len(lst) // 2) * 2] = lst[i]
	for i in range(0, len(lst) // 2):
		out[i * 2 + 1] = lst[i]
	c = 0
	for i in range(1, len(lst) - 1, 2):
		if out[i] < out[i - 1] and out[i] < out[i + 1]:
			c += 1
	print(c)
	print(' '.join((str(i) for i in out)))
solve()


n = int(input())
a = list(map(int, input().split()))
a.sort()
ind = n // 2
res = []
i = 0
f = True
for j in range(n):
	if f == True:
		res.append(a[ind])
		ind += 1
		f = False
	else:
		res.append(a[i])
		i += 1
		f = True
ans = 0
for i in range(1, n - 1):
	if res[i - 1] > res[i] and res[i] < res[i + 1]:
		ans += 1
print(ans)
print(*res)


n = int(input())
a = list(map(int, input().split()))
a.sort()
arr = [0 for i in range(n)]
ind = 0
for i in range(1, n, 2):
	arr[i] = a[ind]
	ind += 1
for i in range(0, n, 2):
	arr[i] = a[ind]
	ind += 1
count = 0
for i in range(1, n - 1):
	if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
		count += 1
print(count)
print(*arr)


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
A.sort()
Ans = [None] * N
A1 = A[:(N - 1) // 2][::-1]
A2 = A[(N - 1) // 2:]
for i in range((N - 1) // 2):
	Ans[2 * i + 1] = A1[i]
for i in range(N):
	if Ans[i] is None:
		Ans[i] = A2.pop()
ans = 0
for i in range(1, N - 1):
	if Ans[i - 1] > Ans[i] and Ans[i] < Ans[i + 1]:
		ans += 1
print(ans)
print(*Ans)


n = int(input())
ls = list(map(int, input().split()))
ls.sort()
ReturnLs = []
i = 0
for j in range(n // 2, n):
	ReturnLs.append(ls[j])
	if i != n // 2:
		ReturnLs.append(ls[i])
	i += 1
count = 0
for i in range(1, n - 1, 2):
	if ReturnLs[i] < ReturnLs[i + 1] and ReturnLs[i - 1] > ReturnLs[i]:
		count += 1
print(count)
print(*ReturnLs)


n = int(input())
l = list(map(int, input().split()))[:n]
f = [0] * n
l.sort(reverse=True)
cnt = 0
for i in range(n):
	if i % 2 == 1:
		f[i] = l.pop()
for i in range(n):
	if f[i] == 0:
		f[i] = l.pop()
if n % 2 == 0:
	for i in range(1, n - 2, 2):
		if f[i] < f[i - 1] and f[i] < f[i + 1]:
			cnt += 1
else:
	for i in range(1, n - 1, 2):
		if f[i] < f[i - 1] and f[i] < f[i + 1]:
			cnt += 1
print(cnt)
print(*f)


import math
count = math.ceil(int(input()) / 2) - 1
a = sorted(list(map(int, input().split())))
a1 = a[:count]
a2 = a[-count - 1:]
b = count
c = ''
for (x, y) in zip(a1, a2):
	if x == y:
		count -= 1
	c += str(y) + ' ' + str(x) + ' '
c += str(a[-1]) + ' '
for i in a[b:-b - 1]:
	c += str(i)
print(count)
print(c)


n = int(input())
a = list(map(int, input().split()))
if n <= 2:
	print(0)
	print(' '.join(map(str, a)))
else:
	a.sort()
	b = [0] * n
	j = 0
	for i in range(1, n, 2):
		b[i] = a[j]
		j += 1
	for i in range(0, n, 2):
		b[i] = a[j]
		j += 1
	c = 0
	for i in range(1, n - 1, 2):
		if b[i - 1] > b[i] < b[i + 1]:
			c += 1
	print(c)
	print(' '.join(map(str, b)))


n = int(input())
a = list(map(int, input().split()))
a.sort()
i = 0
j = 0
a1 = a[:n // 2]
a2 = a[n // 2:]
ans = []
while i < len(a1) and j < len(a2):
	ans.append(a2[j])
	j += 1
	ans.append(a1[i])
	i += 1
while i < len(a1):
	ans.append(a1[i])
	i += 1
while j < len(a2):
	ans.append(a2[j])
	j += 1
c = 0
for i in range(1, len(ans) - 1):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		c += 1
print(c)
print(*ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = [None for _ in range(n)]
i = 0
j = 1
while j < n:
	ans[j] = a[i]
	i += 1
	j += 2
k = i
j = 0
while k < n and j < n:
	ans[j] = a[k]
	k += 1
	j += 2
count = 0
for i in range(1, n - 1):
	if ans[i] < ans[i + 1] and ans[i] < ans[i - 1]:
		count += 1
print(count)
print(' '.join(map(str, ans)))


n = int(input())
a = list(sorted(list(map(int, input().split()))))
k = n // 2
b = []
j = k
l = 0
for i in range(n):
	if i % 2 == 0:
		b.append(a[j])
		j += 1
	else:
		b.append(a[l])
		l += 1
c = 0
for i in range(1, n - 1, 2):
	if b[i] < b[i + 1] and b[i] < b[i - 1]:
		c += 1
print(c)
print(*b, sep=' ')


n = int(input())
l = list(map(int, input().split()))
l.sort()
l1 = [0] * n
(j, ans) = (0, 0)
for i in range(1, n, 2):
	l1[i] = l[j]
	j += 1
for i in range(0, n, 2):
	l1[i] = l[j]
	j += 1
for i in range(1, n - 1):
	if l1[i] < l1[i + 1] and l1[i] < l1[i - 1]:
		ans += 1
print(ans)
print(*l1)


def main():
	n = int(input())
	a = map(int, input().split())
	a = sorted(a)
	result = [-1] * n
	i = 0
	j = n - 1 - 1
	l = 0
	r = n - 1
	if n % 2 == 0:
		i += 1
	while j > 0:
		result[i] = a[r]
		result[j] = a[l]
		i += 2
		j -= 2
		r -= 1
		l += 1
	if i < n:
		result[i] = a[r]
	if j >= 0:
		result[j] = a[l]
	cnt = 0
	for r in range(1, len(result) - 1):
		if result[r - 1] > result[r] and result[r] < result[r + 1]:
			cnt += 1
	print(cnt)
	print(*result)
main()


for _ in range(1):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(0)
		print(l[0])
	else:
		l.sort()
		m = [0] * n
		ind = 0
		for i in range(1, n, 2):
			m[i] = l[ind]
			ind += 1
		for i in range(0, n, 2):
			m[i] = l[ind]
			ind += 1
		ans = 0
		for i in range(1, len(m) - 1):
			if m[i - 1] > m[i] and m[i] < m[i + 1]:
				ans += 1
		m1 = [0] * n
		ind = 0
		for i in range(1, n, 2):
			m1[i] = l[ind]
			ind += 1
		ind = n - 1
		for i in range(0, n, 2):
			m1[i] = l[ind]
			ind -= 1
		ans1 = 0
		for i in range(1, len(m) - 1):
			if m1[i - 1] > m1[i] and m1[i] < m1[i + 1]:
				ans1 += 1
		if ans > ans1:
			print(ans)
			print(' '.join((str(x) for x in m)))
		else:
			print(ans1)
			print(' '.join((str(x) for x in m1)))


import math
N = int(input())
arr = [int(i) for i in input().split(' ')]

def win(arr):
	if len(arr) <= 2:
		print(0)
		print(' '.join([str(i) for i in arr]))
		return
	arr.sort()
	maxPossible = math.ceil(len(arr) / 2) - 1
	minArr = arr[:maxPossible]
	maxArr = arr[maxPossible:]
	j = 0
	ans = [maxArr[0]]
	count = 0
	for i in range(1, len(maxArr)):
		if minArr[j] < maxArr[i - 1] and minArr[j] < maxArr[i]:
			count += 1
			ans.append(minArr[j])
			j += 1
		ans.append(maxArr[i])
		if j == len(minArr):
			ans += maxArr[i + 1:]
			break
	if j < len(minArr):
		ans += minArr[j:]
	print(count)
	print(' '.join([str(i) for i in ans]))
win(arr)


from collections import defaultdict as dd
from sys import stdin, stdout
from bisect import bisect_left
from math import log, sqrt
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
a.sort()
k = 0
c = 0
for i in range(1, n, 2):
	ans[i] = a[k]
	k += 1
for i in range(0, n, 2):
	ans[i] = a[k]
	k += 1
for i in range(1, n - 1):
	if ans[i] < ans[i + 1] and ans[i] < ans[i - 1]:
		c += 1
print(c)
print(*ans)


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
resArr = [0] * n
count = 0
j = 0
for i in range(1, n, 2):
	resArr[i] = arr[j]
	j += 1
for i in range(0, n, 2):
	resArr[i] = arr[j]
	j += 1
for i in range(1, n - 1):
	if resArr[i] < resArr[i - 1] and resArr[i] < resArr[i + 1]:
		count += 1
print(count)
print(' '.join(map(str, resArr)))


n = int(input())
s = input()
L = s.split()
for i in range(len(L)):
	L[i] = int(L[i])
myLen = len(L)
if myLen <= 2:
	print(0)
	print(s)
	quit()
L.sort()
gr = myLen // 2
cnt = gr if myLen % 2 else gr - 1
v = L[0]
for i in range(gr, myLen - 1):
	if L[i] > v < L[i + 1]:
		k = i
		break
else:
	print(0)
	print(s)
	quit()
shift = k - gr
L1 = []
for i in range(gr, gr + shift):
	L1.append(L[i])
nn = cnt - shift
for i in range(nn):
	L1.append(L[k + i])
	L1.append(L[i])
L1.append(L[-1])
for i in range(shift):
	L1.append(L[i + nn])
if not myLen % 2:
	L1.append(L[cnt])
nSales = 0
for i in range(1, len(L1), 2):
	if i + 1 < len(L1) and L1[i - 1] > L1[i] < L1[i + 1]:
		nSales += 1
print(nSales)
L1 = [str(e) for e in L1]
print(' '.join(L1))


n = int(input())
d = [int(i) for i in input().split()]
d.sort()
if n < 3 or d.count(d[0]) >= n - 1:
	print(0)
	print(' '.join(map(str, d)))
	exit()
mxd = [min(d[i], d[i + 1]) for i in range(n - 1)]
hi = (n - 3) // 2
lo = 0
while lo < hi:
	mid = (lo + hi + 1) // 2
	kk = n - mid - 2
	if sum((mxd[kk + i] > d[i] for i in range(mid + 1))) == mid + 1:
		lo = mid
	else:
		hi = mid - 1
print(lo + 1)
ans = []
for i in range(lo + 1):
	ans.append(d[n - lo - 2 + i])
	ans.append(d[i])
ans.append(d[-1])
ans.extend(d[lo + 1:n - lo - 2])
print(' '.join(map(str, ans)))


import sys
input = sys.stdin.readline
n = int(input())
x = sorted(list(map(int, input().split())))
(a, b) = (x[:n // 2], x[n // 2:])
tmp = []
for i in range(n // 2):
	tmp.append(b[i])
	tmp.append(a[i])
if n % 2:
	tmp.append(b[-1])
cnt = 0
for i in range(1, n - 1, 2):
	if tmp[i + 1] > tmp[i] < tmp[i - 1]:
		cnt += 1
print(cnt)
print(*tmp)


n = int(input())
a = [int(i) for i in input().split()]
b = [0] * n
a.sort()
j = 0
for i in range(1, n, 2):
	b[i] = a[j]
	j += 1
for i in range(0, n, 2):
	b[i] = a[j]
	j += 1
count = 0
for i in range(1, n - 1):
	if b[i] < b[i - 1] and b[i + 1] > b[i]:
		count += 1
print(count)
print(*b)


from math import ceil
n = int(input())
a = list(map(int, input().split()))
a.sort()
i = 1
cur = 0
res = [0 for i in range(n)]
while i < len(a):
	res[i] = a[cur]
	i += 2
	cur += 1
i = 0
while i < len(a):
	res[i] = a[cur]
	cur += 1
	i += 2
w = 0
for i in range(1, n - 1):
	if res[i] < res[i - 1] and res[i] < res[i + 1]:
		w += 1
print(w)
print(' '.join([str(x) for x in res]))


n = int(input())
(*arr,) = map(int, input().split())
arr.sort()
half = n // 2
res = [-1] * n
if n % 2 == 0:
	res[::2] = arr[-half:]
	res[1::2] = arr[:-half]
else:
	res[::2] = arr[-half - 1:]
	res[1::2] = arr[:-half - 1]
ans = 0
for i in range(1, n - 1):
	if res[i - 1] > res[i] < res[i + 1]:
		ans += 1
print(ans)
print(*res)


n = int(input())
arr = list(map(int, input().split()))
res = [0] * n
arr.sort()
for i in range(n):
	if i < n // 2:
		res[i * 2 + 1] = arr[i]
	else:
		res[(i - n // 2) * 2] = arr[i]
x = 0
for i in range(1, n - 1):
	if res[i - 1] > res[i] < res[i + 1]:
		x += 1
print(x)
print(*res)


n = int(input())
l = list(map(int, input().split()))
lena = len(l)
l.sort()
left = l[:lena // 2]
right = l[lena // 2:]
left.sort()
right.sort()
answer = []
count = 0
for i in range(len(right)):
	answer.append(right[i])
	if i < len(left):
		answer.append(left[i])
		if answer[-1] < answer[-2] and i < len(right) - 1:
			count += 1
print(count)
print(*answer)


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ans = []
p = 0
if n % 2:
	for i in range(n // 2, n):
		ans.append(a[i])
		if i < n - 1:
			ans.append(a[p])
			p += 1
else:
	for i in range(n // 2, n):
		ans.append(a[i])
		ans.append(a[p])
		p += 1
cnt = 0
for i in range(1, n - 1):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		cnt += 1
print(cnt)
print(*ans)


import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split() if i != '\n']
a.sort()
ans = [0] * n
j = 0
for i in range(1, n, 2):
	ans[i] = a[j]
	j += 1
for i in range(n):
	if ans[i] == 0:
		ans[i] = a[j]
		j += 1
count = 0
for i in range(1, n - 1):
	if ans[i - 1] > ans[i] and ans[i + 1] > ans[i]:
		count += 1
print(count)
print(*ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = []
count = 0
c = 0
for i in range(n // 2, n):
	ans.append(a[i])
	if c < n // 2:
		ans.append(a[c])
		c = c + 1
for i in range(1, n, 2):
	if i + 1 < n:
		if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
			count = count + 1
print(count)
print(*ans)


import sys, os.path, math
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(10 ** 5)

def mod():
	return 10 ** 9 + 7

def i():
	return sys.stdin.readline().strip()

def ii():
	return int(sys.stdin.readline())

def li():
	return list(sys.stdin.readline().strip())

def mii():
	return map(int, sys.stdin.readline().split())

def lii():
	return list(map(int, sys.stdin.readline().strip().split()))

def solve():
	a = ii()
	b = sorted(lii())
	c = 0
	d = []
	e = len(b)
	if a % 2 == 0:
		for i in range(int(a / 2)):
			d.append(b[i + int(a / 2)])
			d.append(b[i])
	else:
		b.insert(math.floor(a / 2), ' ')
		for i in range(math.ceil(a / 2)):
			d.append(b[i + math.ceil(a / 2)])
			d.append(b[i])
	if e % 2 == 0:
		for i in range(1, a - 1, 2):
			if d[i - 1] > d[i] < d[i + 1]:
				c += 1
			else:
				pass
		print(c)
		for x in d:
			print(x, end=' ')
	else:
		d.remove(' ')
		for i in range(1, a - 1, 2):
			if d[i - 1] > d[i] < d[i + 1]:
				c += 1
			else:
				pass
		print(c)
		for x in d:
			print(x, end=' ')
for _ in range(1):
	solve()


n = int(input())
arr = list(map(int, input().strip().split()))
if n % 2 == 0:
	ans = n // 2 - 1
else:
	ans = n // 2
arr.sort()
low = arr[:n // 2]
hi = arr[n // 2:]
arr[::2] = hi
arr[1::2] = low
for i in range(1, n - 1, 2):
	if arr[i] == arr[i - 1] or arr[i] == arr[i + 1]:
		ans -= 1
print(ans)
print(*arr, sep=' ')


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
x = n // 2
b = a[:x]
c = a[x:]
c.reverse()
b.reverse()
z = []
for i in range(x):
	z.append(b[i])
	z.append(c[i])
	c[i] = 0
for i in range(len(c)):
	if c[i] != 0:
		z.append(c[i])
ans2 = 0
for i in range(1, n - 1, 2):
	if z[i] < z[i - 1] and z[i] < z[i + 1]:
		ans2 += 1
b = []
x = n // 2
pos = x
if 2 * x != n:
	pos = x + 1
for i in range(x):
	b.append(a[i])
	b.append(a[i + pos])
if 2 * x != n:
	b.append(a[x])
c = []
for i in range(x):
	c.append(a[i])
	c.append(a[-i])
if 2 * x != n:
	c.append(a[x])
ans = 0
for i in range(1, n - 1, 2):
	if b[i] < b[i - 1] and b[i] < b[i + 1]:
		ans += 1
tmp = 0
for i in range(1, n - 1, 2):
	if c[i] < c[i - 1] and c[i] < c[i + 1]:
		tmp += 1
if max(ans, tmp, ans2) == ans:
	print(ans)
	print(*b)
elif max(ans, tmp, ans2) == tmp:
	print(tmp)
	print(*c)
else:
	print(ans2)
	print(*z)


n = int(input())
a = list(map(int, input().split()))
a.sort()
d = [0 for i in range(n)]
i = 0
j = n // 2
for z in range(0, n // 2):
	d[2 * i] = a[j]
	d[2 * i + 1] = a[i]
	i += 1
	j += 1
if j == n - 1:
	d[n - 1] = a[n - 1]
k = 0
for i in range(1, n - 1):
	if d[i] < d[i - 1] and d[i] < d[i + 1]:
		k += 1
print(k)
print(' '.join(list(map(str, d))))


n = int(input())
l = list(sorted(map(int, input().split())))
left = l[0:n // 2]
right = l[n // 2:n]
arr = [-1 for x in range(n)]
count = 0
flag = True
j = 0
k = 0
for i in range(n):
	if flag == True:
		arr[i] = right[j]
		j += 1
		flag = False
	elif flag == False:
		arr[i] = left[k]
		k += 1
		flag = True
for a in range(1, n - 1):
	if arr[a] < arr[a - 1] and arr[a] < arr[a + 1]:
		count += 1
print(count)
print(*arr)


n = int(input())
b = list(map(int, input().split()))
if n < 3:
	print(0)
	print(*b)
else:
	out = 0
	ans = []
	b.sort()
	k = b[:n // 2]
	l = b[n // 2:]
	if n % 2:
		for i in range(n // 2):
			ans.append(l.pop())
			ans.append(k.pop())
		ans.append(l.pop())
		for i in range(1, n, 2):
			if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
				out += 1
		print(out)
		print(*ans)
	else:
		for i in range(len(k)):
			ans.append(k.pop())
			ans.append(l.pop())
		for i in range(2, n, 2):
			if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
				out += 1
		print(out)
		print(*ans)


import sys

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

def mpint():
	return map(int, sys.stdin.readline().split(' '))

def itg():
	return int(sys.stdin.readline())
n = itg()
arr = sorted(mpint())
a1 = arr[n >> 1:]
a2 = arr[:n >> 1]
ans = []
for i in range(n):
	if i & 1:
		ans.append(a2.pop())
	else:
		ans.append(a1.pop())
for i in range(n - 2):
	if ans[i] == ans[i + 1]:
		(ans[i + 1], ans[i + 2]) = (ans[i + 2], ans[i + 1])
ans1 = 0
for i in range(1, n - 1):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		ans1 += 1
print(ans1)
print(*ans)


import time, math as mt, bisect as bs, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

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

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

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * (2 * 10 ** 5 + 5)
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(2 * 10 ** 5 + 5):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return

def readTree(n, e):
	adj = [set() for i in range(n + 1)]
	for i in range(e):
		(u1, u2) = IP()
		adj[u1].add(u2)
	return adj
mod = 10 ** 9 + 7

def solve():
	n = II()
	a = L()
	a.sort()
	ans = [0] * n
	j = n - 1
	for i in range(0, n, 2):
		ans[i] = a[j]
		j -= 1
	ans2 = list(ans)
	not_used = deque()
	for i in range(1, n, 2):
		while ans[i] == 0 and j >= 0:
			if a[j] < ans[i - 1] and a[j] < ans[min(i + 1, n - 1)]:
				ans[i] = a[j]
			else:
				not_used.append(j)
			j -= 1
		if j < 0:
			break
	for i in range(n):
		if ans[i] == 0:
			ans[i] = a[not_used.pop()]
		fin = 0
	for i in range(1, n - 1):
		if ans[i] < ans[i + 1] and ans[i] < ans[i - 1]:
			fin += 1
	P(fin)
	print(*ans)
	return
t = 1
for i in range(t):
	solve()


from math import *
from bisect import *
from collections import *
from random import *
from decimal import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = 1
while t:
	t -= 1
	n = inp()
	a = lis()
	r = [0 for i in range(n)]
	a.sort()
	(i, j) = (0, n // 2)
	for k in range(n):
		if k % 2 ^ 1:
			r[k] = a[j]
			j += 1
		else:
			r[k] = a[i]
			i += 1
	s = 0
	for i in range(1, n - 1):
		if r[i] < r[i - 1] and r[i] < r[i + 1]:
			s += 1
	print(s)
	print(*r)


from sys import stdin
n = int(stdin.readline())
a = sorted(map(int, input().split()))
m = (n - 1) // 2
c = 0
b = []
for i in range(n):
	b.append(a[(1 - i % 2) * (n // 2) + i // 2])
for i in range(1, m + 1):
	if b[i * 2 - 1] < min(b[i * 2 - 2], b[i * 2]):
		c += 1
print(c)
for i in range(n):
	print(b[i], end=' ')


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
x = a[:n // 2]
a = a[n // 2:]
(l, k, m) = ([], 0, 0)
for i in range(n):
	if i % 2 == 0:
		l.append(a[k])
		k += 1
	else:
		l.append(x[m])
		m += 1
m = 0
for i in range(1, n - 1):
	if l[i] < l[i - 1] and l[i] < l[i + 1]:
		m += 1
print(m)
for i in l:
	print(i, end=' ')


def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	l = []
	if n < 3:
		print(0)
		print(*a)
		return
	half = n // 2
	for i in range(half):
		l.append(a[half + i])
		l.append(a[i])
	if n % 2 != 0:
		l.append(a[-1])
	total = 0
	for j in range(1, n - 1):
		if l[j] < l[j - 1] and l[j] < l[j + 1]:
			total += 1
	print(total)
	print(*l)
main()


n = int(input())
list1 = list(map(int, input().split()))
list1.sort()
if n <= 2:
	print(0)
	print(*list1)
else:
	temp = [-1] * len(list1)
	count = 0
	for i in range(1, len(list1), 2):
		temp[i] = list1[count]
		count += 1
	for i in range(0, len(list1), 2):
		temp[i] = list1[count]
		count += 1
	s = 0
	for i in range(1, len(list1) - 1):
		if temp[i] < temp[i - 1] and temp[i] < temp[i + 1]:
			s += 1
	print(s)
	print(*temp)


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
res = [0] * n
res[::2] = a[n // 2:]
res[1::2] = a[:n // 2]
ans = 0
for i in range(1, n - 1):
	ans += res[i - 1] > res[i] < res[i + 1]
print(ans)
print(*res)


n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()
la = l[-1]
k = []
if n < 3:
	print(0)
	print(*l)
elif n % 2 != 0:
	ans = 0
	l1 = l[0:n // 2]
	l2 = l[n // 2:]
	k.append(l[n // 2])
	for i in range(n // 2, n - 1):
		ma1 = l[i]
		ma2 = l[i + 1]
		if l[i - n // 2] < ma1 and l[i - n // 2] < ma2:
			k.append(l[i - n // 2])
			k.append(ma2)
			ans += 1
		else:
			k.append(l[i - n // 2])
			k.append(ma2)
	print(ans)
	print(*k)
else:
	ans = 0
	l1 = l[0:n // 2 - 1]
	l2 = l[n // 2 - 1:]
	k.append(l[n // 2])
	for i in range(n // 2, n - 1):
		ma1 = l[i]
		ma2 = l[i + 1]
		if l[i - n // 2] < ma1 and l[i - n // 2] < ma2:
			k.append(l[i - n // 2])
			k.append(ma2)
			ans += 1
		else:
			k.append(l[i - n // 2])
			k.append(ma2)
	k.append(l[n // 2 - 1])
	print(ans)
	print(*k)


import sys
n = int(input())
lst1 = list(map(int, input().split()))
a = [None] * n
lst1.sort()
index = ans = 0
for i in range(1, n, 2):
	a[i] = lst1[index]
	index += 1
for i in range(0, n, 2):
	a[i] = lst1[index]
	index += 1
for i in range(1, n - 1, 2):
	if a[i] < a[i - 1] and a[i] < a[i + 1]:
		ans += 1
print(ans)
print(*a)


import traceback
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

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')
sys.stdin = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
from collections import defaultdict as dfd, Counter, deque
from functools import lru_cache
from itertools import accumulate

def geti():
	return int(input())

def gets():
	return input()

def getil():
	return list(map(int, input().split()))

def getsl():
	return input().split()

def getinps(s):
	inps = s.split()
	m = {'i': geti, 's': gets, 'il': getil, 'sl': getsl}
	if len(inps) == 1:
		return m[s]()
	return [m[k]() for k in inps]

def get2d(nrows, ncols, n=0):
	return [[n] * ncols for r in range(nrows)]

def get_acc(a):
	return list(accumulate(a))

def get_ncr(n, r, mod=10 ** 9 + 7):
	num = den = 1
	r = min(r, n - r)
	for i in range(r):
		num = num * (n - i) % mod
		den = den * (i + 1) % mod
	return num * pow(den, mod - 2, mod) % mod

def get_nc2(n):
	return n * (n - 1) // 2

def get_npr(n, r):
	if n < r:
		return 0
	return math.factorial(n) // math.factorial(r)

def put(a):
	return ' '.join(map(str, a))
inf = float('inf')
mod = 10 ** 9 + 7

def main():
	((N,), a) = getinps('il il')
	a.sort()
	ans = [0] * N
	p = 0
	for i in range(1, N, 2):
		ans[i] = a[p]
		p += 1
	for i in range(0, N, 2):
		ans[i] = a[p]
		p += 1
	k = 0
	for i in range(1, N - 1):
		k += ans[i - 1] > ans[i] < ans[i + 1]
	print(k)
	print(*ans)
try:
	ans = main()
	ans = str(ans)
except Exception as e:
	print(e)
	traceback.print_exc()


from collections import defaultdict as dd
import math
import sys
import heapq
import copy
input = sys.stdin.readline

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))

def solve():
	n = nn()
	ice = lm()
	ice.sort()
	out = []
	for i in range(n):
		if i % 2 == 1:
			out.append(ice[i // 2])
		else:
			out.append(ice[i // 2 + n // 2])
	good = 0
	for i in range(n - 1):
		if i % 2 == 1:
			if out[i] < out[i + 1] and out[i] < out[i - 1]:
				good += 1
	print(good)
	print(*out)
solve()


R = lambda : map(int, input().split())
n = int(input())
arr = sorted(R(), reverse=True)
vst = [0] * n
res = []
j = 0
k = (n + 1) // 2
cnt = 0
for i in range(n):
	if not vst[i]:
		res.append(arr[i])
		j = max(j, i + 1)
		while j < n and vst[j]:
			j += 1
		k = max(k, j + 1)
		while k < n and (vst[k] or arr[k] >= arr[j]):
			k += 1
		if k < n:
			res.append(arr[k])
			vst[k] = 1
			cnt += 1
print(cnt)
print(' '.join(map(str, res)))


n = int(input())
a = [int(x) for x in input().split()]
b = [0] * n
a.sort()
k = 0
c = 0
for i in range(1, n, 2):
	b[i] = a[k]
	k += 1
for i in range(0, n, 2):
	b[i] = a[k]
	k += 1
for i in range(1, n - 1):
	if b[i] < b[i - 1] and b[i] < b[i + 1]:
		c += 1
print(c)
print(*b)


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ans = [0] * n
for i in range(0, n, 2):
	ans[i] = a.pop()
for i in range(1, n, 2):
	ans[i] = a.pop()
v = 0
flag = 0
for i in range(1, n - int(n & 1 == 0), 2):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		v += 1
	elif n & 1 == 0:
		if ans[-1] < ans[i - 1] and ans[-1] < ans[i + 1]:
			v += 1
			flag = 1
			(ans[-1], ans[i]) = (ans[i], ans[-1])
print(v)
print(*ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
cur = 0
i = 1
res = [0] * n
while i < n:
	res[i] = a[cur]
	i += 2
	cur += 1
i = 0
while i < n:
	res[i] = a[cur]
	i += 2
	cur += 1
ans = 0
for i in range(1, n - 1):
	if res[i - 1] > res[i] and res[i] < res[i + 1]:
		ans += 1
print(ans)
print(*res)


n = int(input())
a = sorted(list(map(int, input().split())))
arr = [0] * n
i = 0
for j in range(n // 2, n):
	arr[i] = a[j]
	i += 2
i = 1
for j in range(n // 2):
	arr[i] = a[j]
	i += 2
cnt = 0
for i in range(1, n - 1):
	if arr[i - 1] > arr[i] < arr[i + 1]:
		cnt += 1
print(cnt)
print(*arr)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
arr = sorted(list(map(int, input().split())))
if n == 0:
	print(0)
	print(*arr)
elif n == 2:
	print(0)
	arr.sort()
	print(*arr)
else:
	ls = [0] * n
	var = 0
	var2 = n // 2
	for i in range(n):
		if (i + 1) % 2 == 0:
			ls[i] = arr[var]
			var += 1
		else:
			ls[i] = arr[var2]
			var2 += 1
	cntt = 0
	for i in range(1, n - 1):
		if ls[i] < ls[i + 1] and ls[i] < ls[i - 1]:
			cntt += 1
	print(cntt)
	print(*ls)


def solve():
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	a.sort()
	a1 = a[:n // 2]
	a2 = a[n // 2:]
	flag = True
	cursor1 = 0
	cursor2 = 0
	prevPrice = -100
	ans = 0
	for i in range(len(a2)):
		if i + 1 < len(a2):
			ans += 1 if a2[i] > a1[i] and a1[i] < a2[i + 1] else 0
	print(ans)
	for i in range(n):
		if not flag:
			print(a1[cursor1], end=' ')
			cursor1 += 1
		else:
			print(a2[cursor2], end=' ')
			cursor2 += 1
		flag = not flag
t = 1
for _ in range(t):
	solve()


n = int(input())
A = [int(x) for x in input().split()]
A.sort()
R = [None] * n
R[1::2] = A[:n // 2]
R[0::2] = A[n // 2:]
r = 0
for i in range(1, n - 1):
	r += R[i - 1] > R[i] < R[i + 1]
print(r)
print(*R)


n = int(input())
list1 = list(map(int, input().split()))
list1 = sorted(list1)
res = []
first = list1[:n // 2]
second = list1[n // 2:]
c = 0
if n % 2 == 0:
	for i in range(len(second)):
		res.append(second[i])
		res.append(first[i])
else:
	for i in range(len(second) - 1):
		res.append(second[i])
		res.append(first[i])
	res.append(second[-1])
for i in range(n - 1):
	if res[i] < res[i - 1] and res[i] < res[i + 1]:
		c += 1
print(c)
for num in res:
	print(num, end=' ')


def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(n, l) = (inp(), inlt())
res = []
l.sort()
for i in range(n // 2):
	if i + n // 2 < n:
		res.append(l[i + n // 2])
		res.append(l[i])
if n % 2:
	res.append(l[-1])
cnt = 0
for i in range(1, len(res) - 1):
	if res[i - 1] > res[i] < res[i + 1]:
		cnt += 1
print(cnt)
print(' '.join([str(x) for x in res]))


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
n = I()
l = L()
l.sort()
b = [0] * n
(b[::2], b[1::2]) = (l[n // 2:], l[:n // 2])
print(sum((b[i - 1] > b[i] < b[i + 1] for i in range(1, n - 1))))
print(*b)


n = int(input())
p = [int(x) for x in input().split()]
p.sort()
a = [None] * n
k = 0
if n % 2 == 1:
	for i in range(1, n, 2):
		a[i] = p[k]
		k += 1
	for i in range(0, n, 2):
		a[i] = p[k]
		k += 1
else:
	for i in range(1, n, 2):
		a[i] = p[k]
		k += 1
	for i in range(0, n, 2):
		a[i] = p[k]
		k += 1
ct = 0
for i in range(1, n - 1):
	if a[i] < a[i - 1] and a[i] < a[i + 1]:
		ct += 1
print(ct)
for e in a:
	print(e, end=' ')
print()


n = int(input())
a = sorted(map(int, input().split()))
l = [a[(1 - i % 2) * (n // 2) + i // 2] for i in range(n)]
c = 0
for i in range(1, n - 1):
	if l[i - 1] > l[i] < l[i + 1]:
		c += 1
print(c)
print(' '.join(map(str, l)))


n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = []
if n % 2 == 1:
	ans.append(l[n // 2])
	for i in range(n // 2):
		ans.append(l[i])
		ans.append(l[(n + 1) // 2 + i])
else:
	for i in range(n // 2):
		ans.append(l[(n + 1) // 2 + i])
		ans.append(l[i])
num = 0
for i in range(1, n - 1):
	if ans[i] < min(ans[i - 1], ans[i + 1]):
		num += 1
print(num)
print(' '.join(map(str, ans)))


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
a1 = [0] * n
cnt = 0
a1[0] = a[n // 2]
if n % 2 != 0:
	for i in range(0, n // 2):
		a1[i * 2 + 1] = a[i]
		a1[i * 2 + 2] = a[n // 2 + i + 1]
else:
	for i in range(0, n // 2 - 1):
		a1[1 + i * 2] = a[i]
		a1[i * 2 + 2] = a[n // 2 + i + 1]
	a1[n - 1] = a[n // 2 - 1]
if n == 1:
	print(0)
	print(a1[0])
else:
	s = str(a1[0]) + ' '
	for i in range(1, n - 1):
		s += str(a1[i]) + ' '
		if a1[i] < a1[i + 1] and a1[i] < a1[i - 1]:
			cnt += 1
	s += str(a1[n - 1])
	print(cnt)
	print(s)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ind = 0
ans = [0] * n
cnt = 0
for i in range(1, n, 2):
	ans[i] = a[ind]
	ind += 1
for i in range(0, n, 2):
	ans[i] = a[ind]
	ind += 1
for i in range(1, n - 1):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		cnt += 1
print(cnt)
print(*ans)


def do(l, n):
	o = l[0:n // 2]
	k = l[n // 2:n]
	nlist = []
	for i in range(n // 2):
		nlist.append(str(k[i]))
		nlist.append(str(o[i]))
	if n % 2 == 1:
		nlist.append(str(k[n // 2]))
	return nlist
num = int(input())
l = list(map(int, input().split()))
l.sort()
a = do(l, num)
cnt = 0
for i in range(1, num - 1):
	if int(a[i - 1]) > int(a[i]) and int(a[i + 1]) > int(a[i]):
		cnt += 1
print(cnt)
print(' '.join(a))


from sys import *
input = stdin.readline
listInput = lambda : list(map(int, input().strip().split()))
lineInput = lambda : map(int, input().strip().split())
sJoin = lambda a, sep: f'{sep}'.join(a)
arrJoin = lambda a, sep: f'{sep}'.join(map(str, a))

def main():
	n = int(input())
	arr = sorted(listInput())
	k = set(arr)
	a = arr[:n // 2]
	b = arr[n // 2:]
	l = list(zip(b, a))
	ans = []
	j = 1
	c = 0
	for i in l:
		ans.append(i[0])
		ans.append(i[1])
	if n % 2 == 1:
		ans.append(arr[-1])
	while j < n - 1:
		if ans[j - 1] > ans[j] < ans[j + 1]:
			c += 1
		j += 2
	print(c)
	print(*ans)
main()


n = int(input())
a = sorted(map(int, input().split()))
b = [0] * n
(b[1::2], b[::2]) = (a[:n // 2], a[n // 2:])
print(sum((b[i - 1] > b[i] < b[i + 1] for i in range(1, n - 1))))
print(*b)


n = int(input())
array = list(map(int, input().split(' ')))
array.sort()
menores = array[:int(n / 2)]
maiores = array[int(n / 2):]
index = 0
solucao = []
qtd = 0
flag_left = False
for i in range(n):
	if i % 2 != 0:
		solucao.append(menores[index])
		if menores[index] < solucao[i - 1]:
			flag_left = True
		else:
			flag_left = False
		index += 1
	else:
		solucao.append(maiores[int(i / 2)])
		if flag_left and maiores[int(i / 2)] > solucao[i - 1]:
			qtd += 1
			flag_left = False
print(qtd)
solucao = [str(int) for int in solucao]
print(' '.join(solucao))


import sys
n = int(sys.stdin.readline())
price = [int(v) for v in sys.stdin.readline().strip().split(' ')]
price.sort()
result = []
start = int(n / 2)
for i in range(0, start):
	result.append(price[i + start])
	result.append(price[i])
if n % 2 == 1:
	result.append(price[n - 1])
num = 0
for i in range(1, n - 1, 2):
	if result[i] < result[i - 1] and result[i] < result[i + 1]:
		num += 1
print(num)
print(' '.join((str(v) for v in result)))


n = int(input())
arr = [int(x) for x in input().split()]
arr.sort()
arr1 = arr[0:n // 2]
arr2 = arr[n // 2:]
arr3 = []
for i in range(n // 2):
	arr3.append(arr2[i])
	arr3.append(arr1[i])
if n % 2 != 0:
	arr3.append(arr2[-1])
ans = 0
for i in range(1, n - 1):
	if arr3[i - 1] > arr3[i] and arr3[i + 1] > arr3[i]:
		ans += 1
print(ans)
print(*arr3)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 0
ansarr = []
if n < 3:
	print(0)
	print(' '.join([str(x) for x in a]))
elif n % 2 == 0:
	for i in range(n // 2):
		ansarr.append(a[n // 2 + i])
		ansarr.append(a[i])
	for i in range(1, len(a) - 1, 2):
		if ansarr[i] < ansarr[i - 1] and ansarr[i] < ansarr[i + 1]:
			ans += 1
	print(ans)
	print(' '.join([str(x) for x in ansarr]))
else:
	for i in range(n // 2):
		ansarr.append(a[n // 2 + i])
		ansarr.append(a[i])
	ansarr.append(a[len(a) - 1])
	for i in range(1, len(a), 2):
		if ansarr[i] < ansarr[i - 1] and ansarr[i] < ansarr[i + 1]:
			ans += 1
	print(ans)
	print(' '.join([str(x) for x in ansarr]))


n = int(input())
arr = list(map(int, input().split(' ')))
arr = list(sorted(arr))
p = n // 2
resultarr = []
i = 0
while p < n:
	resultarr.append(arr[p])
	if i < n // 2:
		resultarr.append(arr[i])
	i += 1
	p += 1
result = 0
for i in range(1, len(arr) - 1):
	if resultarr[i - 1] > resultarr[i] and resultarr[i + 1] > resultarr[i]:
		result += 1
print(result)
print(' '.join(list(map(str, resultarr))))


n = int(input())
a = list(map(int, input().split()))
a.sort()
lo = 0
hi = (n + 1) // 2
while hi - lo > 1:
	test = (hi + lo) // 2
	smol = a[:test]
	large = a[-test - 1:]
	rest = a[test:-test - 1]
	works = True
	for i in range(test):
		if smol[i] == large[i] or smol[i] == large[i + 1]:
			works = False
	if works:
		lo = test
	else:
		hi = test
smol = a[:lo]
large = a[-lo - 1:]
rest = a[lo:-lo - 1]
o = []
while smol:
	o += [large.pop()]
	o += [smol.pop()]
o += large
o += rest
print(lo)
print(' '.join(map(str, o)))


def solve(n, ices):
	ices = sorted(ices)
	(former, latter) = (ices[:n // 2], ices[n // 2:])
	res = 0
	res_ice = []
	for i in range((n - 1) // 2):
		res_ice.append(latter[i])
		res_ice.append(former[i])
		if former[i] < latter[i]:
			res += 1
	res_ice.append(latter[-1])
	if n % 2 == 0:
		res_ice.append(former[-1])
	return (res, ' '.join(list(map(str, res_ice))))

def main():
	n = int(input())
	ices = list(map(int, input().split()))
	(res1, res2) = solve(n, ices)
	print(res1)
	print(res2)
main()


import math
n = int(input())
a = list(map(int, input().split()))
a.sort()
firstPart = []
secondPart = []
firstPartLength = math.floor((n - 1) / 2)
secondPartLength = n - firstPartLength
for i in range(firstPartLength):
	firstPart.append(a[i])
for i in range(firstPartLength, n):
	secondPart.append(a[i])
c = []
secondPartPointer = 0
ans = 0
secondPart.reverse()
firstPart.reverse()
for i in range(firstPartLength):
	before = secondPart[secondPartPointer]
	c.append(before)
	secondPartPointer += 1
	main = firstPart[i]
	c.append(main)
	after = secondPart[secondPartPointer]
	if main < after and main < before:
		ans += 1
for i in range(secondPartPointer, secondPartLength):
	c.append(secondPart[i])
print(ans)
for i in range(n - 1):
	print(c[i], end=' ')
print(c[n - 1])


import sys
n = int(sys.stdin.readline())
pricelist = [int(v) for v in sys.stdin.readline().strip().split(' ')]
pricelist.sort(reverse=True)
newlist = [0 for i in range(0, n)]
start = int((n + 1) / 2)
for i in range(0, start):
	newlist[i * 2] = pricelist[i]
waitlist = []
pt = 1
total = 0
for i in range(start, n):
	if pt < n - 1 and pricelist[i] < newlist[pt - 1] and (pricelist[i] < newlist[pt + 1]):
		newlist[pt] = pricelist[i]
		total += 1
		pt += 2
	else:
		waitlist.append(pricelist[i])
for v in waitlist:
	newlist[pt] = v
	pt += 2
print(total)
print(' '.join((str(v) for v in newlist)))


from sys import stdin, stdout
from math import *
testing = True

def tp(s='\n'):
	if testing:
		stdout.write(s)

def main():
	n = int(stdin.readline())
	arr = [int(i) for i in stdin.readline().split()]
	arr.sort()
	out = [0] * n
	for i in range(floor(n / 2)):
		out[2 * i + 1] = arr[i]
	for i in range(ceil(n / 2)):
		out[2 * i] = arr[i + floor(n / 2)]
	count = 0
	for i in range(1, n - 1):
		if out[i] < out[i + 1] and out[i] < out[i - 1]:
			count += 1
	print(count)
	print(' '.join([str(i) for i in out]))
main()


n = int(input())
a = [int(inp) for inp in input().split()]
a.sort()
i = 0
j = len(a) // 2
b = []
sw = 1
while j < len(a) or i < len(a) // 2:
	if sw:
		b.append(a[j])
		j += 1
	else:
		b.append(a[i])
		i += 1
	sw = 1 - sw
res = 0
i = 1
while i < len(b) - 1:
	if b[i] < b[i - 1] and b[i] < b[i + 1]:
		res += 1
		i += 1
	i += 1
print(res)
print(*b, sep=' ')


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = [0] * n
c = 0
for i in range(1, n, 2):
	b[i] = a[c]
	c += 1
for i in range(0, n, 2):
	b[i] = a[c]
	c += 1
s = 0
for i in range(1, n - 1):
	if b[i] < b[i - 1] and b[i] < b[i + 1]:
		s += 1
print(s)
print(*b)


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = [-1] * n
k = 0
c = 0
for i in range(1, n, 2):
	ans[i] = arr[k]
	k += 1
for i in range(n):
	if ans[i] == -1:
		ans[i] = arr[k]
		k += 1
for i in range(1, n - 1, 2):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		c += 1
print(c)
for i in range(n):
	print(ans[i], end=' ')


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
_a = sorted(array())
a = sorted(list(_a))
small = a[:n // 2]
large = a[n // 2:]
ans = [0] * n
si = 0
li = 0
for i in range(n):
	if i % 2:
		ans[i] = small[si]
		si += 1
	else:
		ans[i] = large[li]
		li += 1
c = 0
for i in range(1, n - 1):
	if ans[i - 1] > ans[i] and ans[i] < ans[i + 1]:
		c += 1
print(c)
print(*ans)


from collections import Counter

def read_line():
	return list(map(int, input().split()))
n = int(input())
l = sorted(read_line())

def ok(ans):
	nums = l[:ans]
	rest = l[ans:]
	if len(rest) < ans + 1:
		return None
	rest = rest[-(ans + 1):]
	l2 = []
	for i in range(len(nums)):
		if nums[i] < rest[i] and nums[i] < rest[i + 1]:
			l2.append(rest[i])
			l2.append(nums[i])
		else:
			return None
	l2.append(rest[-1])
	r = Counter(l)
	s = Counter(l2)
	for v in r:
		k = r[v] - s[v]
		l2 += [v] * k
	return l2

def _ok(ans):
	nums = l[:ans]
	rest = l[ans:]
	if len(rest) < ans + 1:
		return None
	rest = rest[-(ans + 1):]
	for i in range(len(nums)):
		if nums[i] < rest[i] and nums[i] < rest[i + 1]:
			pass
		else:
			return None
	return 1
lo = 0
hi = n
while lo <= hi:
	mid = (lo + hi) // 2
	if _ok(mid) is not None:
		lo = mid + 1
	else:
		hi = mid - 1
a = ok(hi)
print(hi)
print(' '.join(map(str, a)))


from math import *
from random import *
from bisect import *
from math import *
n = int(input())
mas = sorted(list(map(int, input().split())))
otv = [0 for i in range(n)]
nxt = 0
for i in range(1, n, 2):
	otv[i] = mas[nxt]
	nxt += 1
for i in range(0, n, 2):
	otv[i] = mas[nxt]
	nxt += 1
res = 0
for i in range(1, n - 1):
	if otv[i] < otv[i + 1] and otv[i] < otv[i - 1]:
		res += 1
print(res)
print(' '.join(map(str, otv)))


from math import ceil
n = int(input())
l = list(map(int, input().split()))
l.sort()
if len(l) == 1:
	print(0)
	print(*l)
	exit()
ans = [0] * n
c = 0
for i in range(1, n, 2):
	ans[i] = l[c]
	c += 1
for i in range(0, n, 2):
	ans[i] = l[c]
	c += 1
final = 0
for i in range(1, n - 1):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		final += 1
print(final)
print(*ans)


n = int(input())
nums = list(map(int, input().split()))
nums.sort(reverse=True)
res = [None] * n
b = (n - 1) // 2
for i in range(1, n, 2):
	res[i] = nums.pop()
for i in range(0, n, 2):
	res[i] = nums.pop()
b = 0
for i in range(1, n - 1):
	if res[i - 1] > res[i] and res[i] < res[i + 1]:
		b += 1
print(b)
for x in res:
	print(x, end=' ')
print()


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
res = []
for i in range(n // 2):
	res.append(arr[n // 2 + i])
	res.append(arr[i])
if n % 2:
	res.append(arr[-1])
res2 = 0
for i in range(1, n - 1):
	if res[i] < res[i - 1] and res[i] < res[i + 1]:
		res2 += 1
print(res2)
print(' '.join([str(i) for i in res]))


from bisect import bisect_left
import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
from collections import deque
from functools import cmp_to_key
import math
import heapq
import re

def sin():
	return input()

def ain():
	return list(map(int, sin().split()))

def sain():
	return input().split()

def iin():
	return int(sin())
MAX = float('inf')
MIN = float('-inf')
MOD = 1000000007

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	s = set()
	for p in range(2, n + 1):
		if prime[p]:
			s.add(p)
	return s

def readTree(n, m):
	adj = [deque([]) for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = ain()
		adj[u].append(v)
		adj[v].append(u)
	return adj

def main():
	n = iin()
	l = ain()
	l.sort()
	d = [0] * n
	c = 0
	for i in range(1, n, 2):
		d[i] = l[c]
		c += 1
	for i in range(0, n, 2):
		d[i] = l[c]
		c += 1
	ans = 0
	for i in range(1, n - 1, 2):
		if d[i - 1] > d[i] < d[i + 1]:
			ans += 1
	print(ans)
	print(*d)
BUFSIZE = 8192

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')
if os.getcwd() == 'D:\\code':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import math
import random
input = sys.stdin.readline

def inp():
	return int(input())

def inara():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
ara = inara()
ara.sort()
ans = [0] * n
i = 1
j = 0
while i < n:
	ans[i] = ara[j]
	j += 1
	i += 2
i = 0
while j < n:
	ans[i] = ara[j]
	i += 2
	j += 1
tot = 0
for i in range(1, n - 1):
	if ans[i - 1] > ans[i]:
		if ans[i + 1] > ans[i]:
			tot += 1
print(tot)
print(*ans)


from sys import *
input = stdin.readline
for _ in range(1):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = [0] * n
	k = n // 2
	j = k
	for i in range(0, n, 2):
		b[i] = a[j]
		j += 1
	j = 0
	for i in range(1, n, 2):
		b[i] = a[j]
		j += 1
	ans = 0
	for i in range(1, n - 1):
		if b[i] < b[i - 1] and b[i] < b[i + 1]:
			ans += 1
	stdout.write(str(ans) + '\n')
	print(*b)


import sys
input = sys.stdin.readline
n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ans = [-1] * n
num = 0
if n % 2 == 1:
	for i in range(0, n, 2):
		ans[i] = a.pop()
	for i in range(1, n, 2):
		if ans[i - 1] > a[-1] < ans[i + 1]:
			num += 1
		ans[i] = a.pop()
	print(num)
	print(*ans)
else:
	for i in range(0, n, 2):
		ans[i] = a.pop()
	ans[-1] = a.pop()
	for i in range(1, n - 1, 2):
		if ans[i - 1] > a[-1] < ans[i + 1]:
			num += 1
		ans[i] = a.pop()
	print(num)
	print(*ans)


def solve(n, A):
	A.sort()
	v = [0] * n
	j = 0
	for i in range(1, n, 2):
		v[i] = A[j]
		j += 1
	for i in range(0, n, 2):
		v[i] = A[j]
		j += 1
	count = 0
	for i in range(1, n - 1):
		pre = i - 1
		cur = i
		next = i + 1
		if v[pre] > v[cur] and v[next] > v[cur]:
			count += 1
	print(count)
	return v
res = []
n = int(input())
in_ = map(int, input().split(' '))
for c in in_:
	res.append(int(c))
print(*solve(n, res))


n = int(input())
aaa = list(map(int, input().split()))
aaa.sort()
m0 = (n - 1) // 2
m1 = n // 2
ans = 0
order = [0] * n
for i in range(m1, n):
	order[2 * (i - m1)] = aaa[i]
for i in range(m1):
	order[2 * i + 1] = aaa[i]
	if order[2 * i] > order[2 * i + 1]:
		ans += 1
if n % 2 == 0 and order[-2] > order[-1]:
	ans -= 1
print(ans)
print(*order)


n = int(input())
a = sorted(map(int, input().split()))
mas = [0] * n
j = 1
for i in range(n):
	if j >= n:
		j = 0
	mas[j] = a[i]
	j += 2
ans = 0
for i in range(1, n - 1):
	ans += mas[i - 1] > mas[i] < mas[i + 1]
print(ans)
print(*mas)


n = int(input())
a = sorted(map(int, input().split()), reverse=True)
i = n - n // 2
order = [a[0]]
skipped = []
j = 1
while i < n:
	if len(order) % 2:
		while a[i] == a[j]:
			skipped.append(a[i])
			i += 1
			if i == n:
				break
		else:
			order.append(a[i])
			i += 1
	else:
		order.append(a[j])
		j += 1
skipped.extend(a[j:j + n - len(order) - len(skipped)])
purchases = len(order) // 2
if not skipped:
	purchases = max(purchases - 1, 0)
print(purchases)
print(*order + skipped)


t = 1
for _ in range(t):
	n = int(input())
	l = [int(j) for j in input().split()]
	l.sort()
	(c, cnt) = (0, 0)
	k = [0] * n
	for i in range(n // 2):
		k[c] = l[n // 2 + i]
		c += 1
		k[c] = l[i]
		c += 1
	if n % 2 != 0:
		k[n - 1] = l[n - 1]
	for i in range(1, n - 1):
		if k[i - 1] > k[i] and k[i + 1] > k[i]:
			cnt += 1
	print(cnt)
	print(*k)


a = int(input())
b = [int(x) for x in input().split()]
b.sort()
c = []
d = []
result = [0] * a
ans = 0
k = -1
l = 0
m = 0
if a == 1:
	print(0)
	print(*b)
else:
	for i in range(a // 2):
		c.append(b[i])
	for j in range(i + 1, a):
		d.append(b[j])
	while k + 1 != a:
		k += 1
		if (k + 1) % 2 != 0:
			result[k] = d[l]
			l += 1
		else:
			result[k] = c[m]
			m += 1
	for n in range(1, a - 1):
		if result[n] < result[n - 1] and result[n] < result[n + 1]:
			ans += 1
	print(ans)
	print(*result)


n = int(input())
l = [int(i) for i in input().split()]
l.sort()
p = 0
new = []
for i in range(n // 2, n):
	new.append(l[i])
	if p < n // 2:
		new.append(l[p])
		p += 1
x = 0
for i in range(1, n - 1):
	if new[i] < new[i - 1] and new[i] < new[i + 1]:
		x += 1
print(x)
print(*new)


import sys
input = sys.stdin.readline
ins = lambda : input().rstrip()
ini = lambda : int(input().rstrip())
inm = lambda : map(int, input().rstrip().split())
inl = lambda : list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))
n = ini()
a = sorted(inl())
ans = []
count = 0
for i in range(n // 2):
	ans.append(a[i + n // 2])
	ans.append(a[i])
if n % 2:
	ans.append(a[-1])
for i in range(1, n - 1):
	count += 1 if ans[i] < ans[i - 1] and ans[i] < ans[i + 1] else 0
print(count)
print(*ans)


import math
n = int(input())
li = [int(i) for i in input().split()]
li.sort()
if n <= 2:
	print(0)
	print(*li)
	exit(0)
if n & 1:
	p1 = li[:n >> 1]
	p2 = li[n >> 1:]
	aq = []
	for i in range(n):
		if i & 1:
			aq.append(p1.pop())
		else:
			aq.append(p2.pop())
	ac = 0
	for (p, i) in enumerate(aq):
		if p != 0 and p != n - 1 and (i < aq[p - 1]) and (i < aq[p + 1]):
			ac += 1
	print(ac)
	print(*aq)
else:
	p1 = li[:n >> 1]
	p2 = li[n >> 1:]
	ext = p1.pop()
	aq = []
	for i in range(n - 1):
		if i & 1:
			aq.append(p1.pop())
		else:
			aq.append(p2.pop())
	aq.append(ext)
	ac = 0
	for (p, i) in enumerate(aq):
		if p != 0 and p != n - 1 and (i < aq[p - 1]) and (i < aq[p + 1]):
			ac += 1
	print(ac)
	print(*aq)


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = []
f = 0
less = arr[:n // 2]
gre = arr[n // 2:]
l = 0
while l != n // 2:
	ans.append(gre[l])
	ans.append(less[l])
	l += 1
if n % 2 != 0:
	ans.append(gre[-1])
for i in range(1, n - 1):
	if ans[i - 1] > ans[i] and ans[i] < ans[i + 1]:
		f += 1
print(f)
print(*ans)


from sys import *
from collections import deque
n = int(stdin.readline().strip())
things = sorted([int(x) for x in stdin.readline().strip().split(' ')])
count = 0
final = []
big = deque(things[n // 2:])
small = deque(things[:n // 2])
for i in range(len(small)):
	left = big.popleft()
	if big and left > small[0] and (big[0] > small[0]):
		count += 1
		final.append(left)
		final.append(small.popleft())
	else:
		final.append(left)
		final.append(small.pop())
if big:
	final.append(big.pop())
print(count)
print(' '.join(map(str, final)))


from sys import *
input = stdin.readline
listInput = lambda : list(map(int, input().strip().split()))
lineInput = lambda : map(int, input().strip().split())
sJoin = lambda a, sep: f'{sep}'.join(a)
arrJoin = lambda a, sep: f'{sep}'.join(map(str, a))

def main():
	n = int(input())
	arr = sorted(listInput())
	(i, j) = (0, n // 2)
	ans = []
	while i < n // 2:
		ans.append(arr[j])
		ans.append(arr[i])
		i += 1
		j += 1
	if n % 2 == 1:
		ans.append(arr[j])
	c = 0
	j = 1
	while j < n - 1:
		if ans[j - 1] > ans[j] < ans[j + 1]:
			c += 1
		j += 2
	print(c)
	print(*ans)
main()


import sys
input = sys.stdin.readline
N = int(input())
A = [int(_) for _ in input().split()]
sA = sorted(A)
B = ['?'] * N
for i in range(N // 2):
	B[2 * i + 1] = sA[i]
for i in range(N // 2, N):
	B[2 * (i - N // 2)] = sA[i]
answer = 0
for i in range(N // 2):
	if 2 * i + 2 < N:
		if B[2 * i + 1] < B[2 * i] and B[2 * i + 1] < B[2 * i + 2]:
			answer += 1
print(answer)
print(' '.join(map(str, B)))


N = int(input())
List = [int(x) for x in input().split()]
List.sort()
count = 0
arr = [0] * N
index = 0
for i in range(1, N, 2):
	arr[i] = List[index]
	index += 1
for i in range(0, N, 2):
	arr[i] = List[index]
	index += 1
count = 0
for i in range(1, N - 1):
	if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
		count += 1
print(count)
print(*arr)


(z, zz) = (input, lambda : list(map(int, z().split())))
zzz = lambda : [int(i) for i in stdin.readline().split()]
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))
from string import *
from re import *
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f
from bisect import bisect as bs
from bisect import bisect_left as bsl
from itertools import accumulate as ac
from itertools import permutations as permu

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0 and x != 2 or x == 0:
			return 0
	return 1

def dfs(u, visit, graph):
	visit[u] = True
	for i in graph[u]:
		if not visit[i]:
			dfs(i, visit, graph)
num = 1
for _ in range(num):
	n = int(z())
	arr = szzz()
	lst = [-1] * n
	k = n // 2
	for i in range(k):
		lst[i * 2 + 1] = arr[i]
	for i in range(k, n):
		lst[(i - k) * 2] = arr[i]
	ans = 0
	for i in range(1, n - 1):
		if lst[i - 1] > lst[i] and lst[i] < lst[i + 1]:
			ans += 1
	print(ans)
	print(*lst)


n = int(input())
l = list(map(int, input().split()))
l.sort()
if n < 3:
	print(0)
	print(*l)
else:
	arr = [0] * n
	j = 0
	for i in range(1, n, 2):
		arr[i] = l[j]
		j += 1
	for i in range(0, n, 2):
		arr[i] = l[j]
		j += 1
	ans = 0
	for i in range(1, n - 1):
		if arr[i - 1] > arr[i] and arr[i + 1]:
			ans += 1
	print(ans)
	print(*arr)


n = int(input())
a = list(map(int, input().split()))
a.sort()
l = len(a) // 2
f = a[:l]
s = a[l:]
t = [0] * len(a)
ind = 0
for i in range(len(s)):
	t[ind] = s[i]
	ind += 2
ind = 1
for i in range(len(f)):
	t[ind] = f[i]
	ind += 2
x = 0
for i in range(1, len(t) - 1):
	if t[i] < t[i + 1] and t[i] < t[i - 1]:
		x += 1
print(x)
print(' '.join([str(i) for i in t]))


def main():
	n = int(input())
	lst = list(map(int, input().split()))
	lst = sorted(lst)
	new_lst = []
	for i in range(n // 2):
		new_lst.append(lst[n // 2 + i])
		new_lst.append(lst[i])
	if n % 2 == 1:
		new_lst.append(lst[n - 1])
	cnt = 0
	for i in range(1, n - 1):
		if new_lst[i] < new_lst[i - 1] and new_lst[i] < new_lst[i + 1]:
			cnt += 1
	print(cnt)
	line = ''
	for i in new_lst:
		line += str(i) + ' '
	print(line)
t = 1
for i in range(t):
	main()


n = int(input())
arr = [int(el) for el in input().split()]
ans = [0] * n
arr.sort()
take = 0
count = 0
for i in range(1, n, 2):
	ans[i] = arr[count]
	count += 1
for i in range(0, n, 2):
	ans[i] = arr[count]
	count += 1
for i in range(1, n - 1):
	if ans[i - 1] > ans[i] and ans[i + 1] > ans[i]:
		take += 1
print(take)
print(*ans)


n = int(input())
l = sorted(list(map(int, input().split())))
x = []
if n <= 2:
	print(0)
	print(*l)
elif n % 2 == 0:
	a = l[:n // 2]
	b = l[n // 2:]
	ans = 0
	for i in range(n // 2):
		x.append(b[i])
		x.append(a[i])
	for j in range(1, n - 1, 2):
		if x[j] < x[j + 1] and x[j] < x[j - 1]:
			ans += 1
	print(ans)
	print(*x)
else:
	a = l[:n // 2]
	b = l[n // 2:]
	ans = 0
	for i in range(n // 2):
		x.append(b[i])
		x.append(a[i])
	x.append(b[-1])
	for j in range(1, n, 2):
		if x[j] < x[j + 1] and x[j] < x[j - 1]:
			ans += 1
	print(ans)
	print(*x)


t = 1
import random
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr = sorted(arr)
	temp = [0 for x in range(n)]
	c = n - 1
	for i in range(0, n, 2):
		temp[i] = arr[c]
		c -= 1
	c = 0
	for i in range(1, n, 2):
		temp[i] = arr[c]
		c += 1
	ans = 0
	val = n
	if n % 2 == 0:
		val -= 1
	for i in range(1, val, 2):
		if temp[i] < temp[i - 1] and temp[i] < temp[i + 1]:
			ans += 1
	temp2 = [0 for x in range(n)]
	c = 0
	for i in range(1, n, 2):
		temp2[i] = arr[c]
		c += 1
	for i in range(0, n, 2):
		temp2[i] = arr[c]
		c += 1
	ans2 = 0
	for i in range(1, val, 2):
		if temp2[i] < temp2[i - 1] and temp2[i] < temp2[i + 1]:
			ans2 += 1
	if ans2 > ans:
		print(ans2)
		print(*temp2)
	else:
		print(ans)
		print(*temp)


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
small = arr[:len(arr) // 2]
large = arr[len(arr) // 2:]
i = 0
while i < len(arr):
	if i % 2 == 0:
		arr[i] = large[i // 2]
	else:
		arr[i] = small[i // 2]
	i += 1
ans = 0
for i in range(1, len(arr) - 1):
	if arr[i] < arr[i + 1] and arr[i] < arr[i - 1]:
		ans += 1
print(ans)
for i in arr:
	print(i, end=' ')


n = int(input())
l = list(map(int, input().split()))
l.sort()
p = l[0:n // 2]
q = l[n // 2:]
w = []
c = 0
for i in range(n // 2):
	w.append(q[i])
	w.append(p[i])
if n % 2 == 1:
	w.append(q[-1])
for i in range(1, len(w) - 1):
	if w[i] < w[i - 1] and w[i] < w[i + 1]:
		c += 1
print(c)
for i in w:
	print(i, end=' ')
print()


import os
import heapq
import sys, threading
import math
import operator
from collections import defaultdict, deque
from io import BytesIO, IOBase
sys.setrecursionlimit(10 ** 5)

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

def inpt():
	return [int(k) for k in input().split()]

def main():
	n = int(input())
	ar = inpt()
	ar.sort(reverse=True)
	ans = []
	(i, j) = (0, n - 1)
	while i < j:
		ans.append(ar[i])
		ans.append(ar[j])
		i += 1
		j -= 1
	if i == j:
		ans.append(ar[i])
	res = 0
	prev = 1
	for i in range(1, n - 1, 2):
		if ans[i - 1] <= ans[i] or ans[i] >= ans[i + 1]:
			if ans[prev] < ans[i] and ans[prev - 1] > ans[i] < ans[prev + 1]:
				(ans[prev], ans[i]) = (ans[i], ans[prev])
				prev += 2
	for i in range(1, n - 1):
		if ans[i - 1] > ans[i] < ans[i + 1]:
			res += 1
	print(res)
	print(*ans)
BUFSIZE = 8192

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def winner(nums, n):
	nums = sorted(nums)
	ans = []
	i = 0
	j = n // 2
	count = 0
	while j < n:
		ans.append(nums[j])
		if i < n // 2:
			ans.append(nums[i])
			if j != n - 1 and nums[i] != nums[j]:
				count += 1
		j += 1
		i += 1
	return (ans, count)
n = int(input())
(nums, count) = winner([int(i) for i in input().split()], n)
print(count)
for num in nums:
	print(num, end=' ')


import sys, math
n = int(input())
prc = list(map(int, sys.stdin.readline().strip().split()))
prc.sort(reverse=True)
if prc[0] == prc[-1] or len(prc) < 3:
	print(0)
	sys.stdout.write(' '.join(map(str, prc)) + '\n')
else:
	new_prc = []
	for i in range(math.ceil(n / 2)):
		new_prc.append(prc[i])
		if len(new_prc) < n:
			new_prc.append(-1)
	if prc[math.ceil(n / 2) - 1] == prc[math.ceil(n / 2)]:
		(u_bound, l_bound) = (math.ceil(n / 2) - 1, math.ceil(n / 2))
		while u_bound > 0 and prc[u_bound - 1] == prc[u_bound]:
			u_bound -= 1
		while l_bound < n and prc[l_bound] == prc[l_bound + 1]:
			l_bound += 1
		j = math.ceil(n / 2)
		for i in range(1, 2 * (u_bound - 1), 2):
			new_prc[i] = prc[j]
			j += 1
		j = -1
		for i in range(2 * u_bound - 1 if u_bound != 0 else 1, n, 2):
			new_prc[i] = prc[j]
			j -= 1
	else:
		j = math.ceil(n / 2)
		for i in range(1, n, 2):
			new_prc[i] = prc[j]
			j += 1
	count = 0
	for i in range(1, n if n % 2 == 1 else n - 1, 2):
		if new_prc[i - 1] > new_prc[i] and new_prc[i + 1] > new_prc[i]:
			count += 1
	print(count)
	sys.stdout.write(' '.join(map(str, new_prc)) + '\n')


n = int(input())
data = list(map(int, input().split()))

def cal(data, n):
	data.sort()
	res = [0] * n
	m = n // 2
	res[0::2] = data[m:]
	res[1::2] = data[:m]
	ans = 0
	for i in range(1, n, 2):
		if i == n - 1:
			break
		if res[i - 1] > res[i] and res[i] < res[i + 1]:
			ans += 1
	print(ans)
	s = ' '.join(list(map(str, res)))
	print(s)
cal(data, n)


import sys
n = int(input())
spheres = list(map(int, input().split()))
spheres.sort()
small = spheres[:n // 2]
big = spheres[n // 2:]
res = []
for i in range(n):
	if i % 2 == 0:
		res.append(big[i // 2])
	else:
		res.append(small[i // 2])
c = 0
for i in range(n):
	if i == 0 or i == n - 1:
		continue
	if res[i - 1] > res[i] < res[i + 1]:
		c += 1
print(c)
print(*res)


n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0] * n
for i in range((n + 1) // 2 - 1):
	b[2 * i + 1] = a[i]
if n % 2 == 0:
	b[n - 1] = a[n // 2 - 1]
for i in range((n + 1) // 2 - n % 2, n):
	b[2 * i - 2 * ((n + 1) // 2 - n % 2)] = a[i]
cnt = 0
for i in range(n):
	if i > 0 and i < n - 1 and (b[i] < b[i - 1]) and (b[i] < b[i + 1]):
		cnt += 1
print(cnt)
print(' '.join(map(str, b)))


def check_cou(s, x, dx1, dx2):
	if (n := len(s)) - x >= x + 1:
		if s[x - 1] != s[n - x - 1]:
			return True
		elif x - dx1 >= dx2 and dx1 <= n - x + dx2:
			return True
		else:
			return False
	else:
		return False

def cou(s):
	x = int((len(s) - 1) / 2)
	j = x - 1
	while j > 0 and s[j] == s[x - 1]:
		j -= 1
	dx1 = x - 1 - j
	j = n - x - 1
	while j < n - 1 and s[j] == s[n - x - 1]:
		j += 1
	dx2 = j - n + x + 1
	while not check_cou(s, x, dx1, dx2) and x > 0:
		x -= 1
		dx1 -= 1
		dx2 -= 1
	return (x, n - x - 1)

def fu():
	return map(int, input().split(' '))
n = int(input())
s = sorted(list(fu()))
c = cou(s)
p = c[0]
d = c[1]
s1 = s[:p]
sost = s[p:d]
s2 = s[d:]
A = ''
for i in range(p):
	A += str(s2[i]) + ' ' + str(s1[i]) + ' '
for i in range(p, len(s2)):
	A += str(s2[i]) + ' '
for i in range(len(sost)):
	A += str(sost[i]) + ' '
print(p)
print(A[:-1])


import sys
import math
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split(' ')))
A.sort()
X = N // 2
it1 = iter(A[:X])
it2 = iter(A[X:])
x = True
y = True
ans = []
while x or y:
	try:
		ans.append(next(it2))
	except StopIteration:
		x = False
	try:
		ans.append(next(it1))
	except StopIteration:
		y = False
count = 0
for i in range(1, N - 1):
	if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
		count += 1
print(count)
print(' '.join(map(str, ans)))


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = [0] * n
c = 0
for i in range(1, n, 2):
	b[i] = a[c]
	c += 1
for i in range(0, n, 2):
	b[i] = a[c]
	c += 1
s = 0
for i in range(1, n - 1):
	if b[i] < b[i - 1] and b[i] < b[i + 1]:
		s += 1
print(s)
print(*b)


N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * N
for i in range(1, N, 2):
	B[i] = A[i // 2]
Astart = N // 2
Bstart = N - 2 if N % 2 == 0 else N - 1
rem = []
while Astart < N and A[Astart] == B[Bstart - 1]:
	rem.append(A[Astart])
	Astart += 1
for i in range(Bstart, -1, -2):
	if Astart >= N:
		B[i] = rem.pop()
	else:
		B[i] = A[Astart]
		Astart += 1
ans = 0
for i in range(1, N - 1, 2):
	if B[i - 1] > B[i] < B[i + 1]:
		ans += 1
print(ans)
print(*B)


n = int(input())
arr = sorted(list(map(int, input().split())), reverse=True)
t = n - (n - 1) // 2
ans = [0 for _ in range(n)]
for i in range(t):
	x = i * 2
	if x == n:
		x -= 1
	ans[x] = arr[i]
cur = 1
cur2 = n - 2
if n % 2 == 0:
	cur2 -= 1
for i in range(t, n):
	if ans[cur - 1] > arr[i] < ans[cur + 1]:
		ans[cur] = arr[i]
		cur += 2
	else:
		ans[cur2] = arr[i]
		cur2 -= 2
answer = sum((ans[i - 1] > ans[i] < ans[i + 1] for i in range(1, n - 1)))
print(answer)
print(*ans)


def solve(n, ar):
	ar = sorted(ar)
	l = 0
	r = n + 1
	while r - l > 1:
		m = (r + l) // 2
		f = True
		if 2 * m + 1 > n:
			f = False
		else:
			b = []
			pos_a = 0
			pos_b = n - (m + 1)
			for i in range(2 * m + 1):
				if i % 2 == 0:
					b.append(ar[pos_b])
					pos_b += 1
				else:
					b.append(ar[pos_a])
					pos_a += 1
			for i in range(1, 2 * m + 1, 2):
				if b[i - 1] <= b[i] or b[i + 1] <= b[i]:
					f = False
		if f:
			l = m
		else:
			r = m
	print(l)
	pos_a = 0
	pos_b = n - (l + 1)
	b = []
	for i in range(2 * l + 1):
		if i % 2 == 0:
			b.append(ar[pos_b])
			pos_b += 1
		else:
			b.append(ar[pos_a])
			pos_a += 1
	for i in range(pos_a, n - (l + 1)):
		b.append(ar[i])
	print(' '.join(map(str, b)))
n = int(input())
ar = list(map(int, input().split()))
solve(n, ar)


n = int(input())
a = input().split(' ')
if n <= 2:
	print(0)
	print(' '.join(a))
	exit(0)
a = [int(s) for s in a]
a = sorted(a)
b = [0] * n
stepb = 1
for i in range(0, n):
	b[stepb] = a[i]
	stepb += 2
	if stepb >= n:
		stepb = 0
cnt = 0
for i in range(1, n - 1):
	if b[i] < b[i - 1] and b[i] < b[i + 1]:
		cnt += 1
print(cnt)
print(' '.join([str(s) for s in b]))


def check(arr):
	n = len(arr)
	ans = 0
	for i in range(1, n - 1):
		if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
			ans += 1
	return ans
n = int(input())
a = list(map(int, input().split()))
arr = [None] * n
a.sort()
start = 0
for i in range(1, n, 2):
	arr[i] = a[start]
	start += 1
for i in range(n):
	if arr[i] == None:
		arr[i] = a[start]
		start += 1
print(check(arr))
print(*arr)


n = int(input())
lis = sorted(map(int, input().split()))
ans = [0] * n
i = j = n - 1
while j >= 0 and i >= 0:
	ans[j] = lis[i]
	i -= 1
	j -= 2
j = n - 2
tmp = []
while j > 0 and i >= 0:
	while j > 0 and i >= 0 and (ans[j + 1] == lis[i] or ans[j - 1] == lis[i]):
		tmp.append(lis[i])
		i -= 1
	if i >= 0:
		ans[j] = lis[i]
		i -= 1
		j -= 2
j = 0
while i >= 0:
	tmp.append(lis[i])
	i -= 1
for i in range(n):
	if ans[i] == 0:
		ans[i] = tmp[j]
		j += 1
tmp = 0
for i in range(1, n - 1):
	if ans[i - 1] > ans[i] < ans[i + 1]:
		tmp += 1
print(tmp)
print(*ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
x = [x for x in a]
start = 0
for i in range(1, n, 2):
	x[i] = a[start]
	start += 1
for i in range(0, n, 2):
	x[i] = a[start]
	start += 1
ans = 0
for i in range(1, n, 2):
	if i == n - 1:
		continue
	if x[i] < x[i - 1] and x[i] < x[i + 1]:
		ans += 1
print(ans)
print(*x)


n = int(input())
a = list(map(int, input().split()))
a.sort()
b = a[:n // 2]
c = a[n // 2:]
A = []
for i in c:
	A.append(i)
index = 1
indB = 0
while index < n:
	A.insert(index, b[indB])
	indB += 1
	index += 2
index = 1
ans = 0
while index < len(A) - 1:
	if A[index - 1] > A[index] < A[index + 1]:
		ans += 1
	index += 2
print(ans)
answer = ''
for i in A:
	answer += str(i) + ' '
print(answer)


n = int(input())
a = list(map(int, input().split()))
a.sort()
b = n // 2
c = []
i = 0
while len(c) < n:
	c.append(a[b])
	if len(c) == n:
		break
	c.append(a[i])
	i += 1
	b += 1
ans = 0
i = 0
while i < n - 1:
	if c[i] > c[i + 1]:
		ans += 1
	i += 2
if n % 2 == 0 and c[-1] != c[-2]:
	ans -= 1
print(ans)
print(' '.join((str(x) for x in c)))


from __future__ import division, print_function
import os
import sys
from difflib import SequenceMatcher
from io import BytesIO, IOBase
from collections import Counter, deque
from heapq import heapify, heappush, heappop
from math import gcd, ceil, sqrt, log2, log
from itertools import accumulate, repeat, permutations, compress
from operator import itemgetter
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def rl():
	return list(map(int, input().split()))

def arp(arr):
	return ' '.join([str(i) for i in arr])
n = int(input())
arr = rl()
arr.sort()
if n <= 2:
	print(0)
	print(arp(arr))
else:
	ans = deque([])
	ans1 = deque([])
	for i in range(n):
		if i <= n // 2 - 1:
			ans.append(arr[i])
		else:
			ans1.append(arr[i])
	array = []
	for i in range(n):
		if i & 1:
			array.append(ans.popleft())
		else:
			array.append(ans1.popleft())
	cnt = 0
	if n & 1:
		for i in range(1, n, 2):
			if array[i - 1] > array[i] < array[i + 1]:
				cnt += 1
		print(cnt)
		print(arp(array))
	else:
		for i in range(1, n - 1, 2):
			if array[i - 1] > array[i] < array[i + 1]:
				cnt += 1
		print(cnt)
		print(arp(array))
BUFSIZE = 8192

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))
input = lambda : sys.stdin.readline().rstrip('\r\n')


n = int(input())
a = list(map(int, input().split()))
a.sort()
x = []
j = 0
for i in range(int(n // 2), n):
	x.append(a[i])
	if j < int(n // 2):
		x.append(a[j])
		j += 1
ans = 0
for i in range(1, n - 1):
	if x[i] < x[i + 1] and x[i] < x[i - 1]:
		ans += 1
print(ans)
for i in x:
	print(i, end=' ')
print()


from itertools import zip_longest, chain
n = int(input())
a = [int(s) for s in input().split(' ')]
a.sort(reverse=True)
cnt = 0
ans = [x for x in chain(*zip_longest(a[:n // 2 + 1], a[n // 2 + 1:])) if x]
for i in range(1, n - 1):
	if min(ans[i - 1], ans[i + 1]) > ans[i]:
		cnt += 1
print(cnt)
print(*ans)


n = int(input())
bolas = []
valores = input().split()
cont = 0
for e in range(n):
	bolas.append(int(valores[e]))
bolas.sort()
v1 = bolas[0:n // 2]
v2 = bolas[n // 2:]
v3 = []
for e in range(n // 2):
	v3.append(v2[e])
	v3.append(v1[e])
if n % 2 != 0:
	v3.append(v2[-1])
for e in range(1, n - 1):
	if v3[e - 1] > v3[e] and v3[e] < v3[e + 1]:
		cont += 1
print(cont)
for e in v3:
	print(e, end=' ')


l = []
if 1 == 1:
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = []
	if n % 2 == 0:
		if a[n // 2 - 1] != a[n // 2]:
			print(n // 2 - 1)
			for i in range(n):
				if i % 2 == 0:
					s.append(str(a[i // 2 + n // 2]))
				else:
					s.append(str(a[i // 2]))
			print(' '.join(s))
		else:
			c1 = a[:n // 2].count(a[n // 2])
			c2 = a[n // 2:].count(a[n // 2])
			if n // 2 - c2 - c1 >= 1:
				print(n // 2 - 1)
				for i in range(n):
					if i % 2 == 0:
						s.append(str(a[n - 1 - i // 2]))
					else:
						s.append(str(a[n // 2 - 1 - i // 2]))
				print(' '.join(s))
			else:
				print((n // 2 - c2 + 1) // 2 + n // 2 - c1)
				for i in range(n):
					if i % 2 == 0:
						s.append(str(a[n // 2 + i // 2]))
					else:
						s.append(str(a[i // 2]))
				print(' '.join(s))
	elif a[n // 2] != a[n // 2 - 1]:
		print(n // 2)
		for i in range(n):
			if i % 2 == 0:
				s.append(str(a[n // 2 + i // 2]))
			else:
				s.append(str(a[i // 2]))
		print(' '.join(s))
	else:
		c1 = a[:n // 2].count(a[n // 2])
		c2 = a[n // 2:].count(a[n // 2])
		if n // 2 - c2 - c1 + 1 >= 1:
			print(n // 2)
		else:
			print((n // 2 + 1 - c2 + 1) // 2 + n // 2 - c1)
		for i in range(n):
			if i % 2 == 0:
				s.append(str(a[n // 2 + i // 2]))
			else:
				s.append(str(a[i // 2]))
		print(' '.join(s))


import sys

def answer(n, a):
	a.sort()
	ah = a[n // 2:]
	al = a[:n // 2]
	ans = []
	for i in range(len(ah)):
		if i < len(ah):
			ans.append(ah[i])
		if i < len(al):
			ans.append(al[i])
	num_spheres = 0
	for i in range(1, n - 1):
		if ans[i] < ans[i - 1] and ans[i] < ans[i + 1]:
			num_spheres += 1
	print(num_spheres)
	print(*ans)
	return

def main():
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	answer(n, a)
	return
main()


t = 1
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr = sorted(arr)
	temp = [0 for x in range(n)]
	c = 0
	for i in range(1, n, 2):
		temp[i] = arr[c]
		c += 1
	for i in range(0, n, 2):
		temp[i] = arr[c]
		c += 1
	ans = 0
	val = n
	if n % 2 == 0:
		val -= 1
	for i in range(1, val, 2):
		if temp[i] < temp[i - 1] and temp[i] < temp[i + 1]:
			ans += 1
	print(ans)
	print(*temp)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
res = [0] * n
a = sorted(a, reverse=True)
ai = 0
for i in range(0, n, 2):
	res[i] = a[ai]
	ai += 1
if n % 2 == 0:
	res[-1] = a[ai]
	ai += 1
for i in range(1, n - 1, 2):
	res[i] = a[ai]
	ai += 1
ans = 0
for i in range(n):
	if not (i - 1 >= 0 and i + 1 < n):
		continue
	if res[i] < res[i - 1] and res[i] < res[i + 1]:
		ans += 1
print(ans)
print(*res)


x = int(input())
arr = list(map(int, input().split()))
arr.sort()
temp = []
n = 0
if x % 2 != 0:
	mid = x // 2
	arr1 = arr[:mid]
	arr2 = arr[mid:]
	for i in range(mid):
		temp.append(arr2[i])
		temp.append(arr1[i])
	temp.append(arr[-1])
	for i in range(1, x, 2):
		if temp[i] < temp[i - 1] and temp[i] < temp[i + 1]:
			n += 1
	print(n)
	print(*temp)
else:
	mid = x // 2
	arr1 = arr[:mid]
	arr2 = arr[mid:]
	for i in range(mid):
		temp.append(arr2[i])
		temp.append(arr1[i])
	for i in range(1, x - 1, 2):
		if temp[i] < temp[i - 1] and temp[i] < temp[i + 1]:
			n += 1
	print(n)
	print(*temp)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = [0] * n
(ans[1::2], ans[::2]) = (a[:n // 2], a[n // 2:])
print(sum((ans[i - 1] > ans[i] < ans[i + 1] for i in range(1, n - 1))))
print(*ans)


n = input()
p = [int(x) for x in input().strip().split(' ')]
if len(p) <= 2:
	print(0)
	print(' '.join([str(x) for x in p]))
	exit()
p.sort()
res_list = []
if len(p) % 2 == 0:
	index = int(len(p) / 2)
	if p[index - 1] == p[index - 2]:
		res_list.append(p[index - 1])
		del p[index - 1]
	else:
		res_list.append(p[index])
		del p[index]
res = 0
gap = int((len(p) + 1) / 2)
res_list.append(p[gap - 1])
for i in range(gap - 1):
	if p[i] < res_list[-1] and p[i] < p[i + gap]:
		res += 1
	res_list.append(p[i])
	res_list.append(p[i + gap])
print(res)
print(' '.join([str(x) for x in res_list]))


import sys
n = int(sys.stdin.readline())
pricelist = [int(v) for v in sys.stdin.readline().strip().split(' ')]
pricelist.sort()
newlist = [0 for i in range(0, n)]
start = int(n / 2)
for i in range(0, start):
	newlist[i * 2] = pricelist[i + start]
	newlist[i * 2 + 1] = pricelist[i]
if n % 2 == 1:
	newlist[n - 1] = pricelist[n - 1]
total = 0
for i in range(1, n - 1, 2):
	if newlist[i] < newlist[i - 1] and newlist[i] < newlist[i + 1]:
		total += 1
print(total)
print(' '.join((str(v) for v in newlist)))


n = int(input())
esferas = list(map(int, input().split(' ')))
esferas.sort()
limite = int(n / 2)
menores = esferas[:limite]
maiores = esferas[limite:]
indice = 0
reordenadas = []
compras = 0
esquerda = False
for i in range(n):
	if i % 2 == 0:
		reordenadas.append(maiores[int(i / 2)])
		if esquerda and maiores[int(i / 2)] > reordenadas[i - 1]:
			compras += 1
			esquerda = False
	else:
		reordenadas.append(menores[indice])
		if menores[indice] < reordenadas[i - 1]:
			esquerda = True
		else:
			esquerda = False
		indice += 1
print(compras)
reordenadas = [str(int) for int in reordenadas]
print(' '.join(reordenadas))


n = int(input())
a = sorted(map(int, input().split()))
m = (n - 1) // 2
(i, j) = (0, m + 1)
ans = 0
temp = a[m]
if n < 3:
	print(ans)
	for i in a:
		print(i, end=' ')
else:
	z = n * [0]
	z[::2] = a[n // 2:]
	z[1::2] = a[:n // 2]
	for i in range(m):
		if z[2 * i + 1] < z[2 * i] and z[2 * i + 1] < z[2 * i + 2]:
			ans += 1
	print(ans)
	for i in z:
		print(i, end=' ')