#3055. 刷野 II

刷野 II

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

Zayin 知道许多被压制的咒语,在这场战斗中,他决定使用一个名为” 闪电连击” 的咒语来一口气击败所

有的怪物。让我们看看这个咒语是如何工作的。

• 首先,Zayin 选择一个怪物 i(1 ≤ i ≤ n) 以及咒语的初始力量 x。

• 然后这个咒语会首先击中怪物 i,随后对于除第一个目标怪物外,Zayin 可以选择一个没有被该咒语击

中过,并且与其中一个已经被击中的怪物相邻的怪物。

• 第一个被击中的目标怪物会受到 x 的伤害,第二个目标怪物会受到 x−1 的伤害,第三个受到 x−2 的伤

害,以此类推。不难看出,每个怪物都会被击中恰好一次。

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

Zayin 想展示他作为一个高级巫师的能力,所以他希望在只使用一次咒语就能杀死所有怪物的前提下,使

用最少的初始力量 x。

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

个就可以了。

Format

Input

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

接下来一行 n 个整数,第 i 个整数 ai 表示第 i 个怪物的血量。

Output

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

接下来第二行输出 n 个用空格分割的下标 monster_i(1 ≤ i ≤ n),其中 monster_i 表示第 i 个击中的目标

怪物。

Samples

1 10
19 9 12 5 10 7 16 15 17 12
25
1 2 3 4 5 6 7 8 9 10

Limitation

对于所有测试数据,保证 1 ≤ n ≤ 5 × 10^6 , 1 ≤ ai ≤ 10^9。

image