U116552 快速排序

下面是快速排序模板（错的） ```cpp bool cmp(int a, int b) { return a < b; } void swap(int& a, int& b) { int t = a; a = b; b = t; } void sort(int* a, int l, int r) { if (r-l < 2) return; swap(a[l], a[(l+r)/2]); int p = l+1; for (int i = l+1; i < r; i++) if (cmp(a[i], a[l])) swap(a[i], a[p++]); swap(a[l], a[p-1]); sort(a, l, p-1); sort(a, p, r); } int main() { // input n and a sort(a, 0, n); // output a } ``` 现在要求 $[1,n]$ 这 $n$ 个整数的一个排列 $a$，使得对数组 $a$ 执行上面的代码，`cmp` 函数的执行次数最多。 **如存在多组满足要求的数据，输出字典序最小的一组。**

一个整数 $n$。

一行 $n$ 个数表示数组 $a$。

#### 数据范围 数据点1，$n\le 10$ 数据点2，$n\le 100$ 数据点3，$n\le 2\times 10^4$ 数据点4，$n\le 2\times 10^5$ 数据点5，$n\le 10^6$