(挺丢人的, 看了editorial 也没把二分写对.)

贪心地讲, 我们可以把最小的 \(k\) 个元素放在局部最小值, 最大的 \(k+1\) 个元素放在相应的局部最大值. 问题在于有元素相等的情况下, 这个 \(k\) 的值并不方便确定. 注意到答案具有单调性(能有 \(k\) 个必然可以有 \(k-1\) 个), 而且如果给定 \(k\) 来验证能不能取到是简单的. 这样就可以二分答案.

二分的时候应当注意, 总是保持左端点 \(l\) 是满足性质的, 右端点 \(r\) 是不满足性质的, 总是要求 \(l<r-1\), 这样就可以在 \(r==l+1\) 的时候恰好退出, 保证答案就是 \(l\).

下面是代码.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

#include <cstring>

#include <stdint.h>

using namespace std;

inline void io_speed_up()
{
	cin.tie(nullptr);
	cin.sync_with_stdio(false);
	cout.tie(nullptr);
}

#ifndef ONLINE_JUDGE
#define TRACE
#endif
#ifdef TRACE
#define trace(...) __trace__(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __trace__(const char *name, Arg1 &&arg1)
{
	cout << "[#]";
	cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __trace__(const char *names, Arg1 &&arg1, Args &&... args)
{
	cout << "[#]";
	const char *comma = strchr(names + 1, ',');
	cout.write(names, comma - names) << " : " << arg1 << " | ";
	__trace__(comma + 1, args...);
}
#else
#define trace(...) ;
#endif

const int MAXN = (int)1e5 + 5;

bool bin_search(vector<int> arr, int k, int n)
{
	if (2 * k + 1 > n)
	{
		return false;
	}
	bool flag = true;
	vector<int> b;
	int u = 0, v = n - 1 - k;
	for (int i = 0; i < 2 * k + 1; ++i)
	{
		if (i & 1)
		{
			b.emplace_back(arr[u++]);
		}
		else
		{
			b.emplace_back(arr[v++]);
		}
	}
	for (int i = 1; i < 2 * k + 1; i += 2)
	{
		if (b[i] >= b[i + 1] || b[i] >= b[i - 1])
		{
			flag = false;
			break;
		}
	}
	return flag;
}

int main()
{
	io_speed_up();

	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int l = 0, r = n + 1;
	int mid;
	while (l < r - 1)
	{
		mid = (l + r) >> 1;
		if (bin_search(a, mid, n))
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	int ans = l;
	cout << ans << endl;
	vector<int> b;
	int u = 0, v = n - 1 - ans;
	for (int i = 0; i < 2 * ans + 1; ++i)
	{
		if (i & 1)
		{
			b.emplace_back(a[u++]);
		}
		else
		{
			b.emplace_back(a[v++]);
		}
	}
	for (int i = u; i < n - 1 - ans; ++i)
	{
		b.emplace_back(a[i]);
	}
	for (int i = 0; i < b.size(); ++i)
	{
		cout << b[i];
		if (i < (int)b.size() - 1)
		{
			cout << " ";
		}
	}
	cout << endl;
	return 0;
}