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

题目描述

徐老师最近准备让同学们玩一个很有趣的接力赛游戏

他选出了 $n$ 个同学组成一个队伍 $A$，其中每个同学的能力值分别为 $a_1 \sim a_n$

现在他可以在这 $n$ 名同学中 任选 若干名同学，并让他们按照 任意顺序 排成一排，形成一个新的队伍 $B$，序号依次为 $1,2,3 \dots$

在这个新的队伍中每个同学的能力值会受到来自序号小于自身，且 初始能力值 低于自身 初始能力值 的同学的 能力托举。

同样的，若是存在序号小于自身，且 初始能力值 高于自身 初始能力值 的同学，则会限制他能力的发挥。

形式化的说，对于新的队伍 $B$ 中序号为 $i$ 的同学：

1. 每个同学的最终能力值 $b_i$ 一开始的值等于初始能力值 $a_i$
2. 每存在一个编号 $j$ 满足 $j < i$ 且 $a_j < a_i$ 的同学，就会使得 $i$ 同学的最终能力值 $+k$
3. 每存在一个编号 $j$ 满足 $j < i$ 且 $a_j > a_i$ 的同学，就会使得 $i$ 同学的最终能力值 $-k$

其中 $k$ 是个固定的常数

现在徐老师想知道，如何选人可以使得最终新队伍 $B$ 的最终能力值之和最大？

请输出最大的最终能力值之和，以及排序的方案（原队伍 $A$ 中的序号）

输入格式

输入第一行包含两个整数 $n,k$，含义如题

输入第二行包含 $n$ 个整数，分别用空格隔开，依次为 $a_1 \sim a_n$，分别表示原队伍中每个同学的初始能力值

输出格式

输出第一行包含一个整数表示最大的最终能力值之和

输出第二行包含若干个整数，表示队伍 $B$ 的排队顺序（每个同学以原队伍 $A$ 中的序号表示），若存在多种不同的方案，则输出字典序最小的排队顺序

数据范围

对于所有数据保证： $1 \leq n \leq 10^6, 0 \leq k \leq 10^6, -10^6 \le a_i \le 10^6$

样例输入1

3 1
1 2 3

样例输出1

9
1 2 3

样例解释1

最终能力值分别为 $1,3,5$

样例输入2

6 6
1 1 4 5 1 4

样例输出2

82
1 2 5 3 6 4