[GDKOI2024 DAY 1普及组] 刷野 II

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

普及组 第一试

2024 年 1 月 6 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。

Zayin 知道许多被压制的咒语，在这场战斗中，他决定使用一个名为” 闪电连击” 的咒语来一口气击败所有的怪物。让我们看看这个咒语是如何工作的。

• 首先，Zayin 选择一个怪物 $i(1 \leq i \leq n)$ 以及咒语的初始力量 $x$。
• 然后这个咒语会首先击中怪物 $i$，随后对于除第一个目标怪物外，Zayin 可以选择一个没有被该咒语击中过，并且与其中一个已经被击中的怪物相邻的怪物。
• 第一个被击中的目标怪物会受到 $x$ 的伤害，第二个目标怪物会受到 $x-1$ 的伤害，第三个受到 $x-2$ 的伤害，以此类推。不难看出，每个怪物都会被击中恰好一次。

如果一个怪物受到的伤害不低于其生命值，则视为死亡。

Zayin 想展示他作为一个高级巫师的能力，所以他希望在只使用一次咒语就能杀死所有怪物的前提下，使用最少的初始力量 $x$。

现在你需要求出所需的最少的初始力量，并给出一个方案。如果有多个不同的方案，只需要给出任意一个就可以了。

输入格式

第一行包含两个整数 $d, n$，表示测试点编号和怪物数。

接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个怪物的血量。

输出格式

第一行输出一个整数 $x$，表示最少的初始力量。

接下来第二行输出 $n$ 个用空格分割的下标 $monster_i(1 \leq i \leq n)$，其中 $monster_i$ 表示第 $i$ 个击中的目标怪物。

样例 #1

样例输入 #1

1 10
19 9 12 5 10 7 16 15 17 12

样例输出 #1

25
1 2 3 4 5 6 7 8 9 10

提示

对于所有测试数据，保证 $1 \leq n \leq 5 \times 10^6$ ，$1 \leq a_i \leq 10^9$。