CF187E Heaven Tour

故事并没有像 PMP 想象的那样结束。上帝又给了他一次转生的机会，让他能够重获新生。但在他能够回来之前，上帝告诉他，PMP 必须向包括著名程序员在内的 $n$ 位伟人询问他们的人生经历。 这些人站在一条直线上。他们按照从左到右的顺序编号为 $1$ 到 $n$。第 $i$ 个人的位置坐标为 $x_i$，其中 $x_i < x_{i+1}$，$i < n$。PMP 需要以任意顺序逐一拜访所有这些人，每个人只能被拜访一次。旅行开始时，他位于第 $s$ 个人的位置，并首先向他询问经验。 每次 PMP 想要改变自己的位置时，他都必须向一位天使交一张票，然后天使带他飞到目的地。天使将 PMP 从一个位置带到另一个位置，将他放下，其间不会拜访其他人。从第 $i$ 个人移动到第 $j$ 个人需要花费 $|x_i - x_j|$ 的时间。当 PMP 拜访完所有人后，就可以复活。 有两种天使：一种天使只向右飞行，只接受右票，另一种只向左飞行，只接受左票。这两种天使的数量都是无限的。PMP 有 $l$ 张左票和 $n-1-l$ 张右票。 PMP 想以最快的速度拜访所有人，好能参加今年的总决赛（而不是错过的去年决赛）。他想知道拜访所有人的最短时间，并需要知道该如何移动。

输入的第一行包含三个用空格分隔的整数 $n, l, s$，表示需要拜访的人数、PMP 拥有的左票数、以及他起始的人的编号。 第二行包含 $n$ 个用空格分隔的整数，第 $i$ 个整数 $x_i$ 表示第 $i$ 个人的位置坐标（其中 $0 = x_1 < x_2 < \cdots < x_n \leq 10^9$）。 $2 \leq n \leq 10^5$，$0 \leq l < n$，$1 \leq s \leq n$。

如果 PMP 拥有的票数不足以拜访所有人，则输出一行 $-1$。 否则，第一行输出 PMP 完成全部拜访的最短时间。 第二行输出 $n-1$ 个整数，表示在一种最优方案下，PMP 依次拜访的人的编号（除初始位置外）。如果有多种答案，输出任意一种即可。

在这里缅怀一位伟大的竞赛者，他在一年前离开了我们。愿 Renat Mullakhanov 安息。 由 ChatGPT 5 翻译