#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//less_equal to ordered multiset
class SegmentTree {
private:
vector<int> tree;
vector<int> arr;
int n;
// Build the segment tree recursively
void build(int node, int start, int end)
{
if (start == end)
{
tree[node] = arr[start];
}
else
{
int mid = (start + end) / 2;
build(2 * node + 1, start, mid);
build(2 * node + 2, mid + 1, end);
tree[node] = max(tree[2 * node + 1] , tree[2 * node + 2]);
}
}
// Update the value at index 'idx' to 'val' recursively
void update(int node, int start, int end, int idx, int val) {
if (start == end)
{
arr[idx] = val;
tree[node] = val;
}
else
{
int mid = (start + end) / 2;
if (idx >= start && idx <= mid)
{
update(2 * node + 1, start, mid, idx, val);
}
else
{
update(2 * node + 2, mid + 1, end, idx, val);
}
tree[node] = max(tree[2 * node + 1] , tree[2 * node + 2]);
}
}
// Query the sum in the range [l, r] recursively
int query(int node, int start, int end, int l, int r)
{
if(r < start || l > end)
{
return 0; // Out of range
}
if(l <= start && r >= end)
{
return tree[node]; // Current segment is fully within the query range
}
int mid = (start + end) / 2;
int left = query(2 * node + 1, start, mid, l, r);
int right = query(2 * node + 2, mid + 1, end, l, r);
return max(left , right);
}
public:
// Constructor to initialize the segment tree with an array
SegmentTree(vector<int>& input)
{
n = input.size();
arr = input;
tree.resize(4 * n); // Assuming a maximum size for the tree
build(0, 0, n - 1);
}
// Update the value at index 'idx' to 'val'
void update(int idx, int val)
{
update(0, 0, n - 1, idx, val);
}
// Query the sum in the range [l, r]
int query(int l, int r)
{
return query(0, 0, n - 1, l, r);
}
};
void solve()
{
int n,d;
cin>>n>>d;
const int N=5e5+10;
vector<int> v(n);
vector<int> dp(N+5,0);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
SegmentTree st(dp);
int ans=0;
for(int i=0;i<n;i++)
{
int lb=max(0LL,v[i]-d),ub=min(N,v[i]+d);
int mx=st.query(lb,ub);
dp[v[i]]=max(dp[v[i]],mx+1);
st.update(v[i],dp[v[i]]);
ans=max(ans,dp[v[i]]);
}
cout<<ans<<endl;
}
signed main(){
FastIO;
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
int t=1;
// cin>>t;
for(int i=1;i<=t;i++)
{
//cout<<"Case #"<<i<<": ";
solve();
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgZW5kbCAiXG4iCiNkZWZpbmUgRmFzdElPIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKE5VTEwpOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwovLyAjaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+Ci8vICNpbmNsdWRlIDxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPgovLyB1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKLy8gI2RlZmluZSBvcmRlcmVkX3NldCB0cmVlPGludCwgbnVsbF90eXBlLGxlc3M8aW50PiwgcmJfdHJlZV90YWcsdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPgovL2xlc3NfZXF1YWwgdG8gb3JkZXJlZCBtdWx0aXNldApjbGFzcyBTZWdtZW50VHJlZSB7CnByaXZhdGU6CiAgICB2ZWN0b3I8aW50PiB0cmVlOwogICAgdmVjdG9yPGludD4gYXJyOwogICAgaW50IG47CgogICAgLy8gQnVpbGQgdGhlIHNlZ21lbnQgdHJlZSByZWN1cnNpdmVseQogICAgdm9pZCBidWlsZChpbnQgbm9kZSwgaW50IHN0YXJ0LCBpbnQgZW5kKQogICAgewogICAgICAgIGlmIChzdGFydCA9PSBlbmQpCiAgICAgICAgewogICAgICAgICAgICB0cmVlW25vZGVdID0gYXJyW3N0YXJ0XTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgaW50IG1pZCA9IChzdGFydCArIGVuZCkgLyAyOwogICAgICAgICAgICBidWlsZCgyICogbm9kZSArIDEsIHN0YXJ0LCBtaWQpOwogICAgICAgICAgICBidWlsZCgyICogbm9kZSArIDIsIG1pZCArIDEsIGVuZCk7CiAgICAgICAgICAgIHRyZWVbbm9kZV0gPSBtYXgodHJlZVsyICogbm9kZSArIDFdICwgdHJlZVsyICogbm9kZSArIDJdKTsKICAgICAgICB9CiAgICB9CgogICAgLy8gVXBkYXRlIHRoZSB2YWx1ZSBhdCBpbmRleCAnaWR4JyB0byAndmFsJyByZWN1cnNpdmVseQogICAgdm9pZCB1cGRhdGUoaW50IG5vZGUsIGludCBzdGFydCwgaW50IGVuZCwgaW50IGlkeCwgaW50IHZhbCkgewogICAgICAgIGlmIChzdGFydCA9PSBlbmQpCiAgICAgICAgewogICAgICAgICAgICBhcnJbaWR4XSA9IHZhbDsKICAgICAgICAgICAgdHJlZVtub2RlXSA9IHZhbDsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgaW50IG1pZCA9IChzdGFydCArIGVuZCkgLyAyOwogICAgICAgICAgICBpZiAoaWR4ID49IHN0YXJ0ICYmIGlkeCA8PSBtaWQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHVwZGF0ZSgyICogbm9kZSArIDEsIHN0YXJ0LCBtaWQsIGlkeCwgdmFsKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHVwZGF0ZSgyICogbm9kZSArIDIsIG1pZCArIDEsIGVuZCwgaWR4LCB2YWwpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHRyZWVbbm9kZV0gPSBtYXgodHJlZVsyICogbm9kZSArIDFdICwgdHJlZVsyICogbm9kZSArIDJdKTsKICAgICAgICB9CiAgICB9CgogICAgLy8gUXVlcnkgdGhlIHN1bSBpbiB0aGUgcmFuZ2UgW2wsIHJdIHJlY3Vyc2l2ZWx5CiAgICBpbnQgcXVlcnkoaW50IG5vZGUsIGludCBzdGFydCwgaW50IGVuZCwgaW50IGwsIGludCByKQogICAgewogICAgICAgIGlmKHIgPCBzdGFydCB8fCBsID4gZW5kKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIDA7IC8vIE91dCBvZiByYW5nZQogICAgICAgIH0KICAgICAgICBpZihsIDw9IHN0YXJ0ICYmIHIgPj0gZW5kKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIHRyZWVbbm9kZV07IC8vIEN1cnJlbnQgc2VnbWVudCBpcyBmdWxseSB3aXRoaW4gdGhlIHF1ZXJ5IHJhbmdlCiAgICAgICAgfQogICAgICAgIGludCBtaWQgPSAoc3RhcnQgKyBlbmQpIC8gMjsKICAgICAgICBpbnQgbGVmdCA9IHF1ZXJ5KDIgKiBub2RlICsgMSwgc3RhcnQsIG1pZCwgbCwgcik7CiAgICAgICAgaW50IHJpZ2h0ID0gcXVlcnkoMiAqIG5vZGUgKyAyLCBtaWQgKyAxLCBlbmQsIGwsIHIpOwogICAgICAgIHJldHVybiBtYXgobGVmdCAsIHJpZ2h0KTsKICAgIH0KCnB1YmxpYzoKICAgIC8vIENvbnN0cnVjdG9yIHRvIGluaXRpYWxpemUgdGhlIHNlZ21lbnQgdHJlZSB3aXRoIGFuIGFycmF5CiAgICBTZWdtZW50VHJlZSh2ZWN0b3I8aW50PiYgaW5wdXQpCiAgICB7CiAgICAgICAgbiA9IGlucHV0LnNpemUoKTsKICAgICAgICBhcnIgPSBpbnB1dDsKICAgICAgICB0cmVlLnJlc2l6ZSg0ICogbik7IC8vIEFzc3VtaW5nIGEgbWF4aW11bSBzaXplIGZvciB0aGUgdHJlZQogICAgICAgIGJ1aWxkKDAsIDAsIG4gLSAxKTsKICAgIH0KCiAgICAvLyBVcGRhdGUgdGhlIHZhbHVlIGF0IGluZGV4ICdpZHgnIHRvICd2YWwnCiAgICB2b2lkIHVwZGF0ZShpbnQgaWR4LCBpbnQgdmFsKQogICAgewogICAgICAgIHVwZGF0ZSgwLCAwLCBuIC0gMSwgaWR4LCB2YWwpOwogICAgfQoKICAgIC8vIFF1ZXJ5IHRoZSBzdW0gaW4gdGhlIHJhbmdlIFtsLCByXQogICAgaW50IHF1ZXJ5KGludCBsLCBpbnQgcikKICAgIHsKICAgICAgICByZXR1cm4gcXVlcnkoMCwgMCwgbiAtIDEsIGwsIHIpOwogICAgfQp9OwoKdm9pZCBzb2x2ZSgpCnsKICAgIGludCBuLGQ7CiAgICBjaW4+Pm4+PmQ7CiAgICBjb25zdCBpbnQgTj01ZTUrMTA7CiAgICB2ZWN0b3I8aW50PiB2KG4pOwogICAgdmVjdG9yPGludD4gZHAoTis1LDApOwogICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgIHsKICAgICAgICBjaW4+PnZbaV07CiAgICB9CiAgICBTZWdtZW50VHJlZSBzdChkcCk7CiAgICBpbnQgYW5zPTA7CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgewogICAgICAgIGludCBsYj1tYXgoMExMLHZbaV0tZCksdWI9bWluKE4sdltpXStkKTsKICAgICAgICBpbnQgbXg9c3QucXVlcnkobGIsdWIpOwogICAgICAgIGRwW3ZbaV1dPW1heChkcFt2W2ldXSxteCsxKTsKICAgICAgICBzdC51cGRhdGUodltpXSxkcFt2W2ldXSk7CiAgICAgICAgYW5zPW1heChhbnMsZHBbdltpXV0pOwogICAgfQogICAgY291dDw8YW5zPDxlbmRsOwp9CgpzaWduZWQgbWFpbigpewogICAgRmFzdElPOwogICAgLy8gI2lmbmRlZiBPTkxJTkVfSlVER0UKICAgIC8vICAgICBmcmVvcGVuKCJpbnB1dC50eHQiLCAiciIsIHN0ZGluKTsKICAgIC8vICAgICBmcmVvcGVuKCJvdXRwdXQudHh0IiwgInciLCBzdGRvdXQpOwogICAgLy8gI2VuZGlmCiAgICBpbnQgdD0xOwogICAgLy8gY2luPj50OwogICAgZm9yKGludCBpPTE7aTw9dDtpKyspCiAgICB7CiAgICAgICAgLy9jb3V0PDwiQ2FzZSAjIjw8aTw8IjogIjsKICAgICAgICBzb2x2ZSgpOwogICAgfQogICAgcmV0dXJuIDA7Cn0=