Pillars

题意翻译

- 给定序列 $a$，长度为 $n$。 - 找出一个 $a$ 序列的子序列 $b$（设其长度为 $m$），使得 - 对于任意的 $1\le i<m$，有 $|b_{i+1}-b_i|\ge d$。 - $m$ 最大。 - 其中 $d$ 是给定的。 - 您的程序要输出 $m$ 和序列 $b$。 - $1\le n\le 10^5$，$0\le d\le 10^9$，$1\le a_i\le 10^{15}$。若 $b$ 不唯一，输出任意一种。

题目描述

Marmot found a row with $ n $ pillars. The $ i $ -th pillar has the height of $ h_{i} $ meters. Starting from one pillar $ i_{1} $ , Marmot wants to jump on the pillars $ i_{2} $ , ..., $ i_{k} $ . ( $ 1<=i_{1}<i_{2}<...<i_{k}<=n $ ). From a pillar $ i $ Marmot can jump on a pillar $ j $ only if $ i<j $ and $ |h_{i}-h_{j}|>=d $ , where $ |x| $ is the absolute value of the number $ x $ . Now Marmot is asking you find out a jump sequence with maximal length and print it.

输入输出格式

输入格式

The first line contains two integers n and d (1 ≤ n ≤ 10^5, 0 ≤ d ≤ 10^9). The second line contains n numbers h1, h2, ..., hn (1 ≤ hi ≤ 10^15).

输出格式

The first line should contain one integer k, the maximal length of a jump sequence. The second line should contain k integers i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n), representing the pillars' indices from the maximal length jump sequence. If there is more than one maximal length jump sequence, print any.

输入输出样例

输入样例 #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 

说明

In the first example Marmot chooses the pillars $ 1 $ , $ 2 $ , $ 3 $ , $ 5 $ with the heights $ 1 $ , $ 3 $ , $ 6 $ , $ 4 $ . Another jump sequence of length $ 4 $ is $ 1 $ , $ 2 $ , $ 4 $ , $ 5 $ .