CF1419D2 Sage's Birthday (hard version)

这是该问题的困难版本。与简单版本的区别在于，简单版本中所有价格 $a_i$ 都不相同。只有在你解决了两个版本的问题后，才能进行 hack。 今天是 Sage 的生日，她要去购物购买冰球。商店里有 $n$ 个冰球，排成一排，从左到右编号为 $1$ 到 $n$。每个冰球都有一个正整数价格。在本版本中，某些价格可能相同。 如果一个冰球的价格严格小于其左右相邻的两个冰球（即最靠近它左边和右边的冰球），那么这个冰球就是“便宜的”。最左边和最右边的冰球都不算便宜的。Sage 会选择所有便宜的冰球，然后只购买这些冰球。 你可以在 Sage 之前到商店，并随意重新排列这些冰球。请你求出 Sage 最多能买到多少个冰球，并给出冰球的最优排列方式。

第一行包含一个整数 $n$ $(1 \le n \le 10^5)$，表示商店里的冰球数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$，表示每个冰球的价格。

第一行输出 Sage 最多能买到的冰球数量。 第二行输出冰球的最优排列方式。如果有多种答案，可以输出任意一种。

在样例中，无论如何排列冰球，都无法让 Sage 买到 $4$ 个冰球。如果将冰球按 $(3, 1, 4, 2, 4, 2, 5)$ 的顺序排列，Sage 会买到一个价格为 $1$ 的冰球和两个价格为 $2$ 的冰球。 由 ChatGPT 4.1 翻译