题目描述

小武最近学习了快速排序，写出了下述的代码:

void Qsort(int a[], int low, int high)
{
if(low >= high) return;
int first = low;
int last = high;
int key_index = (rand() % (high - low + 1)) + low;
swap(a[first], a[key_index]);
int key = a[first]; /*用数组的第一个记录作为中枢*/
while(first < last) {
while(first < last && a[last] >= key) --last;
a[first] = a[last]; /*将比第一个小的移到低端*/
while(first < last && a[first] <= key) ++first;
a[last] = a[first]; /*将比第一个大的移到高端*/
}
a[first] = key; /*中枢记录到位*/
Qsort(a, low, first - 1);
Qsort(a, first + 1, high);
}

这里开始low=0，high=N，数组a为1-N的一个排列 我们采用随机优化的快速排序是很难碰到最坏情况的，但是小林偷偷修改了运行环境，控制了随机数的生成，使得随机数依次为a1,a2,a3,...,ak,a1,...,即随机数结果依次为a1到ak，然后不断循环。但是还有一个问题，什么样的排列在这样的随机数下效果最差呢，小林认为效果最差即递归的深度最深，但小林不知道怎么找到这个排列，只好交给了你.

输入

第一行两个整数N和k 接下来k行，每行一个数字，表示a1到ak

输出

N行整数，为1-N的一个排列，若有多个排列满足条件，输出其中字典序最小的那个排列