2023 年上海市大学生程序设计竞赛 - 六月赛

有 $n$ 个士兵需要被排成一排。由于每两个士兵的身高都互不相同，因此我们用 $1,2,\cdots n$ 这 $n$ 个整数来分别表示他们的身高，不妨设第 $i$ 个士兵的身高为 $i$ ，$(1\le i\le n)$。

现在，队列中身高为 $1,2,\cdots m$ 的 $m$ 个士兵的位置已经确定，你需要确定剩下 $n-m$ 个士兵的位置，确定完毕之后，你得到一个士兵的队形： $p_1,p_2,\cdots p_n$ 。

接下来，首长会从你编排的队形中等概率随机抽取一个连续的区间 $(l,r)$ ，$1\le l\le r\le n$，他会检查 $p_l,p_{l+1},\cdots p_r$ 这个区间的士兵们能否组成一列良好的小队。一列士兵被称为良好的小队，当且仅当他们中最高的一个士兵站在排头或者排尾。例如，当 $n=5$ 时，如果士兵的队形是 $1,3,5,2,4$ ，那么当首长抽取 $(1,3)$ 时，就得到一支良好的小队，因为 $1,3,5$ 中最高的士兵处于排尾 ；当首长抽取 $(3,5)$ 时，也得到一支良好的小队，因为 $5,2,4$ 中最高的士兵处于排头；而当首长抽取 $(2,4)$ 时，就不能得到一支良好的小队，因为 $3,5,2$ 中最高的士兵既不处于排头也不处于排尾。

你希望首长在抽查的时候抽中一列良好的小队的概率尽可能大，请你给出最优的编排方案。