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; }