CF1419D2.Sage's Birthday (hard version)

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.

这是该问题的困难版本。两个版本的区别在于：在简单版本中，所有价格 $a_i$ 均互不相同；当且仅当你同时解决了该问题的两个版本时，你才可以进行 hack。

今天是 Sage 的生日，她将去商店购买冰球。全部 $n$ 个冰球排成一行，从左到右依次编号为 $1$ 到 $n$。每个冰球都有一个正整数价格。在本版本中，部分价格可以相等。

若一个冰球的价格严格小于其左右两个相邻冰球（即紧邻左侧与紧邻右侧的冰球）的价格，则称该冰球为“便宜的”。最左侧和最右侧的冰球不可能是便宜的。Sage 将选出所有便宜的冰球，并且只购买它们。

你可以在 Sage 到来之前先去商店，并按任意顺序重新排列这些冰球。请找出 Sage 最多能买多少个冰球，并给出一种达到该最大值的冰球重排方案。

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.

第一行包含一个整数 $n$ $(1 \le n \le 10^5)$ —— 商店中冰球的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$ —— 冰球的价格。

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.

第一行输出 Sage 最多能购买的冰球数量。

第二行按最优顺序输出冰球的价格。如果存在多个正确答案，输出任意一个即可。

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.

在样例中，无法以任何顺序摆放冰球，使得 Sage 购买其中的 $4$ 个。若冰球按顺序 $(3, 1, 4, 2, 4, 2, 5)$ 排列，则 Sage 将以单价 $1$ 购买一个冰球，以单价 $2$ 购买两个冰球。