@sunzz3183 和 @TRZ_2007 的题解给出的代码实现细节有问题，在 $n$ 个数字全相等且 $k = O(n)$ 时，时间复杂度会退化到 $O(n^2)$。

以下是一个简单的 gen：

#include<cstdio>

int main()
{
	int n = 2e6;
	printf("%d %d\n",n,n-1);
	for(int i=1;i<=n;++i)
		printf("1 ");
	return 0;
}

我个人比较容易理解的方法是三路分划，即左边是小于基准数的元素，中间是等于基准数的元素，右边是大于基准数的元素。