Pillars

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.

Input

The first line contains two integers n and d (1 ≤ n ≤ 105, 0 ≤ d ≤ 109).

The second line contains n numbers h 1, h 2, …, h n (1 ≤ h i ≤ 1015).

Output

The first line should contain one integer k, the maximal length of a jump sequence.

The second line should contain k integers i 1, i 2, …, i k (1 ≤ i 1 < i 2 < … < i k ≤ n), representing the pillars’ indices from the maximal length jump sequence.

If there is more than one maximal length jump sequence, print any.

Examples

input

5 2
1 3 6 7 4

output

4
1 2 3 5

input

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

output

6
1 4 6 7 8 9

Note

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.

Solution:

#include <cstring>
#include <vector>
#include  <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

using namespace std;

const int N = 400010;

int n;
int ma[N], pa[N];
int ml[N], pl[N];
int mr[N], pr[N];

void modify(int q, int v, int p) {
if (v > ma[q]) {
ma[q] = v;
pa[q] = p;
}
int x = q;
while (x <= n) {
    if (v > ml[x]) {
ml[x] = v;
pl[x] = p;
}
x = (x | (x - 1)) + 1;
}
x = q;
while (x > 0) {
if (v > mr[x]) {
mr[x] = v;
pr[x] = p;
}
x &= x - 1;
}
}

int find_max(int ll, int rr, int &pos) {
int mx = -1;
pos = -1;
int x = ll;
while ((x | (x - 1)) + 1 <= rr) {
    if (mr[x] > mx) {
mx = mr[x];
pos = pr[x];
}
x = (x | (x - 1)) + 1;
}
if (ma[x] > mx) {
mx = ma[x];
pos = pa[x];
}
x = rr;
while ((x & (x - 1)) >= ll) {
if (ml[x] > mx) {
mx = ml[x];
pos = pl[x];
}
x &= x - 1;
}
return mx;
}

long long h[N];
pair <long long, int> a[N];
int pz[N];
int f[N], fp[N];

int main() {
int d;
scanf("%d %d", &n, &d);
for (int i = 1; i <= n; i++) {
    scanf("%I64d", h + i);
    a[i] = make_pair(h[i], i);
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    pz[a[i].second] = i;
  }
  for (int i = 1; i <= n; i++) {
    ma[i] = 0; pa[i] = 0;
    ml[i] = 0; pl[i] = 0;
    mr[i] = 0; pr[i] = 0;
  }
  int ans = -1, km = -1;
  for (int i = 1; i <= n; i++) {
    f[i] = 1;
    fp[i] = 0;
    int pos;
    int from = (lower_bound(a + 1, a + n + 1, make_pair(h[i] + d, 0)) - a);
    if (from <= n) {
      int u = find_max(from, n, pos) + 1;
      if (u > f[i]) {
f[i] = u;
fp[i] = pos;
}
}
int to = (lower_bound(a + 1, a + n + 1, make_pair(h[i] - d, n + 1)) - a) - 1;
if (to >= 1) {
int u = find_max(1, to, pos) + 1;
if (u > f[i]) {
f[i] = u;
fp[i] = pos;
}
}
modify(pz[i], f[i], i);
if (f[i] > ans) {
ans = f[i];
km = i;
}
}
vector <int> ret;
while (km > 0) {
ret.push_back(km);
km = fp[km];
}
printf("%d\n", ans);
for (int i = ans - 1; i > 0; i--) {
printf("%d ", ret[i]);
}
printf("%d\n", ret[0]);
return 0;
}