← 返回题目列表

Codeforces · 474/E

E. 支柱

中文机器翻译题面 查看原题

Marmot 发现了一排有 n 根柱子。第 i 根柱子的高度为 hi 米。从一根柱子 i1 开始,土拨鼠想要跳到柱子 i2,...,ik。 (1 ≤ i1 < i2 < ... < ik ≤ n)。仅当 i < j 且 |hi - hj| 时,土拨鼠才能从柱子 i 跳到柱子 j 上。 ≥ d,其中 |x|是数字 x 的绝对值。

现在 Marmot 要求您找出最大长度的跳转序列并打印它。

输入

第一行包含两个整数 n 和 d (1 ≤ n ≤ 105, 0 ≤ d ≤ 109)。

第二行包含 n 个数字 h1, h2, ..., hn (1 ≤ hi ≤ 1015)。

输出

第一行应包含一个整数 k,即跳转序列的最大长度。

第二行应包含 k 个整数 i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n),表示最大长度跳跃序列中的支柱索引。

如果存在多个最大长度跳转序列,则打印任何一个。

示例

输入 #1

5 2
1 3 6 7 4

输出 #1

4
1 2 3 5

输入 #2

10 3
2 1 3 6 9 11 7 3 20 18

输出 #2

6
1 4 6 7 8 9

注意

在第一个示例中,Marmot 选择高度为 1、3、6、4 的柱子 1、2、3、5。另一个长度为 4 的跳跃序列是 1、2、4、5。