Problem:


Score : 400 points

Problem Statement

You are given a sequence A_1, A_2, ..., A_N and an integer K.

Print the maximum possible length of a sequence B that satisfies the following conditions:

B is a (not necessarily continuous) subsequence of A.

For each pair of adjacents elements of B, the absolute difference of the elements is at most K.

Constraints

1 \leq N \leq 300,000

0 \leq A_i \leq 300,000

0 \leq K \leq 300,000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1
A_2
:
A_N

Output

Print the answer.

Sample Input 1

10 3
1
5
4
3
8
6
9
7
2
4

Sample Output 1

7

For example, B = (1, 4, 3, 6, 9, 7, 4) satisfies the conditions.

It is a subsequence of A = (1, 5, 4, 3, 8, 6, 9, 7, 2, 4).

All of the absolute differences between two adjacent elements (|1-4|, |4-3|, |3-6|, |6-9|, |9-7|, |7-4|) are at most K = 3.



Sample input:
10 3
1
5
4
3
8
6
9
7
2
4


Sample output:
7

Submission status: Wrong Answer

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
# Original source code : 

"""
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

#define all($) begin($), end($)
#define rall($) rbegin($), rend($)

template <class M, class F>
class SegmentTree {
 public:
  SegmentTree(const std::vector<M>& data, M ie, F f)
      : ie_(ie), data_(data), f_(f) {
    build();
  }

  void update(int pos, M val) {
    assert(0 <= pos && pos < n_);
    pos += n_;
    node_[pos] = val;
    while (pos > 0) {
      pos >>= 1;
      node_[pos] = f_(node_[2 * pos], node_[2 * pos + 1]);
    }
  }

  // return f_[l, r)
  // if l >= r, return ie_
  M get(int l, int r) {
    assert(0 <= l && l < n_ && 0 <= r && r < n_ + 1);
    M vl = ie_, vr = ie_;
    for (l += n_, r += n_; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f_(vl, node_[l++]);
      if (r & 1) vr = f_(node_[--r], vr);
    }
    return f_(vl, vr);
  }

  M operator[](int pos) const {
    assert(0 <= pos && pos < n_);
    return node_[n_ + pos];
  }

 private:
  int n_;
  M ie_;
  std::vector<M> data_;
  std::vector<M> node_;
  F f_;

  void build() {
    int sz = data_.size();
    n_ = 1;
    while (n_ < sz) n_ <<= 1;
    node_.assign(2 * n_, ie_);
    for (int i = 0; i < sz; ++i) node_[i + n_] = data_[i];
    for (int i = n_ - 1; i > 0; --i) node_[i] = f_(node_[2 * i], node_[2 * i + 1]);
  }
};

template <class T>
inline void eraque(std::vector<T>& vec) {
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  return;
}

template <class T>
inline int lower_position(const std::vector<T>& vec, T val) {
  return static_cast<int>(std::distance(
      vec.begin(), std::lower_bound(vec.begin(), vec.end(), val)));
}

template <class T>
inline int upper_position(const std::vector<T>& vec, T val) {
  return static_cast<int>(std::distance(
      vec.begin(), std::upper_bound(vec.begin(), vec.end(), val)));
}

template <class T>
inline std::string to_binary(T n) {
  assert(n > 0);
  std::string ret = "";
  while (n) ret += (n & 1) ? '1' : '0', n >>= 1;
  std::reverse(ret.begin(), ret.end());
  return ret;
}

template <class T>
inline void println(T val) {
  std::cout << val << '\n';
}

template <class T>
inline void println(const std::vector<T>& vec) {
  int sz = vec.size();
  for (int i = 0; i < sz; ++i) std::cout << vec[i] << " \n"[i == sz - 1];
}

inline void Yes(bool cond) {
  println(cond ? "Yes" : "No");
}

inline void YES(bool cond) {
  println(cond ? "YES" : "NO");
}

template <class T>
using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

template <class T, class U>
std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {
  return is >> p.first >> p.second;
}

template <class Tuple, std::size_t... Is>
void tuple_in(std::istream& is, Tuple& tp, std::index_sequence<Is...>) {
  ((is >> std::get<Is>(tp)), ...);
}

template <class... Args>
std::istream& operator>>(std::istream& is, std::tuple<Args...>& tp) {
  tuple_in(is, tp, std::index_sequence_for<Args...>{});
  return is;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k; cin >> n >> k;
  vector<int> a(n); cin >> a;

  vector<int> bv(303030, 0);
  int ie = 0;
  auto f = [](int x, int y){ return max(x, y); };
  SegmentTree seg(bv, ie, f);

  vector<int> dp(303030, 0);

  for (int i = 0; i < n; ++i) {
    int cur = a[i];
    int l = max(0, cur - k);
    int r = min(cur + k, n);
    dp[cur] = max(dp[cur], seg.get(l, r + 1) + 1);
    seg.update(cur, dp[cur]);
  }

  cout << *max_element(all(dp)) << endl;

  return 0;
}

"""

import base64
import subprocess
import zlib


exe_bin = "c%1E9eQ;CPmA_AxZDEWg6O%aP1C=<b-GE|&Ar`@jWlQkX%ErYuAs^%+OET6*mR#uxOqNY(jg!1OqRvh>%Wm5Zoz3o~?QE8v-RWjB-NYZ^qn&1INH@zgp<&VhQb+>L2LT$;p7Y+l@_WyErS0@ju17le{O&pD-h1xHd-v-2F<)SfiQ@=MCFE{`+;O|Yw@`e{Sr7rNiOhlTo5@Y240y9jPEXHsT52iOqv$o66kbnnBwEU;XelvHuP@M2LL3D>Y-`<33R-uQLqpHfdN-D8^-NT+h3d6Xc}DG2k5Se?GyQZ^Tu;43OU;yao)E*B|F3HlUQYu=OPSu+L9dMb@re#ESx@UT^2<@$UPjqC+!2fRu57#`7G4^Q#?wPfhniL{UD@bNC7jFTHrc7{+KwJs9>?3HYI8Nku-x9W?D?wA@4g=SQLVrJ@plGKo_Kx_$}S)?<AxsQK$8t?^`6SM)U)Nx<g9c6KJ$y<Ck^oDprXY^@V_#U?=isthAWQmF~CO+@OKRC-((;kGr(^#z%2&&W`lYc5w;?<sms95iw3yez|LI;_=^VZxeM%9k?To|L(#I+iTN)?!8d<N!E4xrh54Ei!=c-6$2q!^2*Q?uL|jOT!K5e%MDTaF3*ksIvL%`lBgyXewpbz_=??bBB1&2DlKVTlqREtReN@gSVksZyy2QpvJRI|fx<r>N)E`U=Vlo&NQ~r?8w;r(Ny}?v8BqUN|G7=o{cMIJOg0E|(AgeA9MdPwHu_>BJ2_PD2^v9#3*X7$P3%KqS1hGGv*al@`AsCA#LRb)vb#B$^xmKjM$3w!lsMrr34M!8cUhMbKkT4iYrV{aBEGljnwl;uTeA_^=O50eajiE$ZL?3Pmg@hEk&_#rv__k;~EUb^D(gP7J3^Ct=TSE^Eq5g-3zF;&4KroexfTJlF8VU+QF)|bt$v|WvG`O8&eNk-FBj8v8t<ljL2!cn}wzUb%oegAdz~9;?EORy%a;}-|GUp1?wsE7U)i1c5%N2OzM$l^{xciu3$5Fn`G*=3rGI?Jrmv<vY3V9CxeB8`@?YwRKT$CE8^N9obURvG)pXz9I9zK~4QS6zgpDn|k?g-`63!`&z$2(TgH_3Y&+lSxy_lHYyr^``!vHou@*qTqNJll`i^W}JzLK}4WK5DQ@hwr8G7KavR{PZG);$B;#T4zU9xJ`v0SK(DEJgdUh>-MY)zea_hSK-wv+)mqt-Jhqz*?Pyv^a2&m);r?Ys_=elznsiGyD$x^aP>oENQIkK_)ZnBe*bt<g{z;xV=BB{h3`?}78Sl%h0jspFR1Ve6~0e}&sE_ssqjh_KCZ&8D*TWNx2te|_yY?+TDpIMgYYBcqA5Sk55H!aBKZ}I0m|Q63*WXyEs#ULA60V4^N?;`h&;MFH!bt?kw+Kj#$~<&d7NUoeKK!C9$lT=EAtntfkzkT#$^6u<k7XcoihJE^4Q$mpv=FEJi0QsS>}I@Ji0K~Df35=N7v<AWd7&Kqswv)GCzqtx+>?8`Imw38)JU(Z1D8B@}BOVF7U|aFh6R(wGQ1Qd22Vi#<TN4gU^Vy7CzHlbuIYnVChHKDjv;N(XvWjI+!&h6N-W0$cMIFo1nk^OL-;T!@Kv}p12H9AXEEqs2Y$?Wp6<RY05R;XIlg>i3iQY%CL-cAf7(!=icU}V}Z=l?}GaR?%#?F6**q|C?K85{@rEJ9^P;EyFW;O@aoY==acLafc(;H{>-jg<O9+P9KVA;I^6rsvRz&}bI@BWuS6a)HF9(6PhsA{Ky(1{OPBl;mrU*0ohM4v-SK00?uPDU1*kHR*(X=$K7l@~!7oQZ5^L*3`^!o@PRjlPQP1!t4vQRENdv2`iDg<a<CWfrto*cp3BUdaXO?aEJ|J@cxpDX8V;3b986O$vLs{F%H=)dvN#_HjSpVpb+6LD+KYW0b<wv_~?Vi!fo!q4C+Rzc+eL$-G`}C<%vDTj1kRLhn=sG?$IsB1{JHlu9ysQsme(8|E9=vsc|NJ-n#K{sq)A%gUT|Pb6wrHo~&>S~feZbv)z-()WFTeYcRQ&`m9ZH{2hNJBgj_-axvlCff%F%J=6zvHZj*0Z|pm~;&Beval0Q?FTx$=sfchvizUqFW{z1RbvG~ubA@Y?uadcgtHwsn)4PEMNkx{rK5?XmsS)I@fXXV;W%*99=)b04;4&O)X&W1jEh4tqx*tgZIACv2bsV-5Xo@Jhe7E!w5b|8o<ZIKMrVTRXbsMW6e$&lWi58J^%?;KZuoEEfo6vB2wo-(w5>ujlZE!{@=&j-UBM;~w`LflOe8NYH}zDbHvX_!pWMnDmW|dnC^G<fz=3X<O!7a=n4t1|K)=4^4X{^V5BW`VXIP%a}=fXd0Tw@9~V9zX{&=xXn+4RrAwes}01{N6}HzSsYgPr0qMu!RhbLji!lsGcRRN+Y9za?d~^ifsbLZ!NG@MzGs@<RSuGU@Ao(y2eSd0p2<FgG_#}Dp8dH=S&-jCWaKT;!b|UD)4;$i0@rN}^UH6P_XOKW2ZuxV+U5r~c^>p^@;o%vHwLcEox#><SNjLJtTK&swSS&n0rtQH)qd^(FHPDO5vhV7o;35rA9CqW<vE87qX}1!oNM7n@?vTBql@{x4_4sr4wy~3>n>rVa^L<UpO@#D>#gjui}Iq+m3@KTnHR@}npyE<6O!g>ATKY+t!nE<x%iBXuXsu+{vH;88H?}5VtL}jgq15!Q=~>=`+!9sJ#<m!qpx37T=@?`v%k7Pr#rfI8~Ew;Fa5wm@mFNs4^O|B-KWT$p2V+x*&hI#T>_<jV|`9Ge$cK-7%zN0WgT)Onq4;FGYeM9WX1Dx>1&qU<OS4pedw1CKg3J#^26_)?d%R@O8*fDDKqaDnKa)BHu4MJv^vPA%Kn*Y=D<)7pDDcnAn!iUODDwZ;ZgV_tMVwEw<&*orahaca2M6IZ^9}!<Yg<GslN>R{KVxF9%ko6_8uMv`0!;B_My^mP=l3d(8%7-=EHW_c++?A!_A980Zc-BDxuq71uol;KH{MZ2TFekavZA5`_Cs+%07YOn{s_1q3~V2^m~5vF^4j4FP=va{<Q_UvIla{0sFwzOyw{SJ@<Mx_@)2z^mxE`x1OtzU9<Eu&@K-=0i<(*`V;cI!o;PL?7`1*_&*dKuD6(pfOIh+o%2d(Jo)Ok`Qa&edL2u@j|0ROiAR`HjqfK@^xZ>#+fd$<y~3JUP!zh-y{X7I(vf&5;tUNAk_N}>X2)P6<+$xOnXGoi1qF;D6q5nW$ygF|Nd>#z;bPDCt%+#Z(G}S;5Q&T3$w*{%`x3{RyH~AB4~F4{QWuSjOC0U>jtB4%<!E;_I{>-Mu?8}DEUBwswQ6-NIM5poDx&aJfA=QUdsKTd<69!)jQF2!o4cXpE}kgwk2}ug^UnZ%5M2LLpfRA;Ftxvc1-}{S64(>MfUkx<=vP<{bO+#X1AUE~dFSRHSx>kjJ9k56xn+ziw<C^sZ{uL+c2$3h%M(&d<&S@s&mTttt9^~N=Bu{3+blcDJqz#p%JSO9Ods#O_CUMU@4u+~Abd7MdvB39eye@h^gxBx;+yNST4wG6AL$IpHJ5+4XRd?X!0JbTU>iEY?k;$HH2*g+tycSPQ>(QmQ{uHco-%u^b&r>NtPR6uUh5cF@?~>{wE-}X)d4af+iJD6;fo=@^km_K&j9(_^J`Z7Lsq4=*mg72mj%B>h*HOQu#Vj&KC2^RZnf4uRmxi%9xvmqO~d8w)|RBT$s^a(s;WnR*AC!W5BjS<f8_I=`(}ZVpKvv2E67hxrJq%hqvq0IRFG5U^WLf;CoQE?1$kwT1iA++Fn_uNx_hw#1+S*7>1w)~uBNN$YWj;NcHheGSJ{24`gch+^>JFhmuA?VTn&9%v%Ae_=w<2klxO$7H&CA4%`K#q-S4vZBK9uz+2wo!=^px0!R{)v^fHs(QI6B{!b=0?*<E4{rRqCYOzdvBlinM$cb6vGKlXme?mVxf^teTfzfi7iH`8Z#pRE3yiB=9?$>jcV6uM0L8fq_3dDhOel+V(RU!c7DZuc*l*zdynw1zr*1EqbGZl&~bN}r|lUn%_wr3WZ|lhTuvo};u(eF^+$B=$Q1OKaQORypc=ded<+?YPsq!r8ENd0OUNkGh(i4UP2*`p4KVfzfIz@=GoL2Gd;>FCk)4++3K~TD-I{pS5^dVcu);^1^)3;+DcZ(&BRp^Hqyi6y~)SpIcbpTD+1p6vgKedy(-gAy(ojirWhNg%-Dyy+!e=Li~UhpRfJVrGQ^U#`Ftc#;Xhak``Z3*pIaMwMExM3G51N|Ip&F>K(=KncsP}_`+EjZX;&$ySyI9{lo<RJWKcOTPWUafcMI_>|`_b+j@%sfa2^&tPK?ZEw#g*4=h~fb6Ng+vVF0m&^}CMT=8~Raf%&#l@`B-;+;DDHj3}n;j1~N-XUGRUz73K<CUa#j_d3^D$CCvccb=yUzVRwo+>hbipl?2ZrJSk`HF03_WV)q$E#<x|0u=v?K~~pnLXb)6FyUGNR4h@O_bp8y|d?`#e}V#Szl~hxz1EPKB3tFkC}?cnS4x8erCPzq7UvT4ea3EZI!8J*1mnrK>jlW+z$Qy64+tCx3cYQ*o^YC_n9Rn#qHc<fZu0;?=MmM%i_$~9n*k;{7wVBTyE#={q}n$ihuOu`$9?axRF;&l=+|^_c!F<<F6+>7i;lflqk5~{!xQ=UZVYV(837C=b4MkI}LE3xp<sR&_I5>S*dr77P7~rWG)^j^PGX5R}AWX-2gvjV8`e(SGd2!<x*Xh`lI(Z;w`AJCl-zR1fO@A9EoxTAthYp3R26rL_{CtTy8<=T<`1dzE4=w)6v%LU)O<=Kvz;<say^J0Sjvb>smblK}e;01-}x$f-y9KCP9cMqVcFmLP;?tru+JwAu<zmB!~k-2!o4KL=eIWVM{F08;l8IF_BCO!SoObB?bm#5it^W-nr7<R9pySXre+enG9|hpaaS6q%Rp9hzQ~IzyOBXs5k+eq7fB@HS0a?(8mrh_Cr|P(IfbH3i96dMDX6%;c54`L77H5tOew_oq`|Mty$CM>lV5_tpOicjez%pMDVYZW0K-RIu!{U1~#>{sDpT}7~Z54*8~;OG8!iI=SOMj>j<Y3LVpk}spG-)LaO*DZ9Ba8I+Kw;XVI`MB{phC-qomyoziy*Bf#|jif<dxH$@wpHDd(Jy4%~>;Ip8wS>1)vV*@Porcx|lJa|m6Er)f5QfYa%6b(jeX;DRR6{6~NcK%Sbo+c^{^l0Fis%~5&g;=|yEu0BF(>b|F)SzKxV37bmZDqun+CCr#dx45ch4!;tG!7;Qi8G!MBTjI~QZcxNa$DkQXKy+h3ong^iOlr}Q~ksl-W~^g3Kf$|$yV@fG!fS@0+b~qu^<Z4++a+^Dq%=4>)eun49qe3mVM<+CgeryjP%nDq(7XT;lO$*Bt(WnkwH-q<^DTob_2x*%R`;PfoKRavO$<Y#0mQvZnnjq7JqWW`x1PV749Vr;>ua#bUeQQt7F3SaoY}^y#9FU(&@8vETgqo(8u4G&gJt7rq9m1jMh<{-RtO&pB+TG!(saDT+C=4rFi`1RQl|`1<y0;SZ#KGE}Wxv=WM<I9wN#eOhLa)OWC=Iwcn(p4-@51hw<z@&L|7aVsVQ4{y#z#pE7-RZfBI;GwJ=u`oD|nw^E*+?-^C=UsptbH&Mr|&)oAd%I?Eh(vQES(`WYuj2_p?+jaCAoj$u)U{vofi;jL@r_atKj3#yWAa*TF{#mEb&JT>v(aG!k|3ji(zwErl=zQITbLjN{L#J=_{}V>_zpB$O+>cN?rmJ7?&!6e^**yxQ%{qDg`gw~e@tN%Ya_0Xr6khLd{rH_CN}Mj!XXoUmn~Jwrum1_r#sJU!zYDEjwSTDfSiAPnKI!j?I~OVZzAM!Kg-*Y49;1Y<Grc}bCVDYkXg}4jq53Vl{i{W%U(PA@>n}E$e!UJacK=`OpHg_LUq>5^&!J^x_Wm(P)pm6nq#J*w?w_CZ^QX!{f5%dV+I0$g{r?BnVIl_"

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Wrong Answer

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
# Original source code : 

"""
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

#define all($) begin($), end($)
#define rall($) rbegin($), rend($)

template <class M, class F>
class SegmentTree {
 public:
  SegmentTree(const std::vector<M>& data, M ie, F f)
      : ie_(ie), data_(data), f_(f) {
    build();
  }

  void update(int pos, M val) {
    assert(0 <= pos && pos < n_);
    pos += n_;
    node_[pos] = val;
    while (pos > 0) {
      pos >>= 1;
      node_[pos] = f_(node_[2 * pos], node_[2 * pos + 1]);
    }
  }

  // return f_[l, r)
  // if l >= r, return ie_
  M get(int l, int r) {
    assert(0 <= l && l < n_ && 0 <= r && r < n_ + 1);
    M vl = ie_, vr = ie_;
    for (l += n_, r += n_; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f_(vl, node_[l++]);
      if (r & 1) vr = f_(node_[--r], vr);
    }
    return f_(vl, vr);
  }

  M operator[](int pos) const {
    assert(0 <= pos && pos < n_);
    return node_[n_ + pos];
  }

 private:
  int n_;
  M ie_;
  std::vector<M> data_;
  std::vector<M> node_;
  F f_;

  void build() {
    int sz = data_.size();
    n_ = 1;
    while (n_ < sz) n_ <<= 1;
    node_.assign(2 * n_, ie_);
    for (int i = 0; i < sz; ++i) node_[i + n_] = data_[i];
    for (int i = n_ - 1; i > 0; --i) node_[i] = f_(node_[2 * i], node_[2 * i + 1]);
  }
};

template <class T>
inline void eraque(std::vector<T>& vec) {
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  return;
}

template <class T>
inline int lower_position(const std::vector<T>& vec, T val) {
  return static_cast<int>(std::distance(
      vec.begin(), std::lower_bound(vec.begin(), vec.end(), val)));
}

template <class T>
inline int upper_position(const std::vector<T>& vec, T val) {
  return static_cast<int>(std::distance(
      vec.begin(), std::upper_bound(vec.begin(), vec.end(), val)));
}

template <class T>
inline std::string to_binary(T n) {
  assert(n > 0);
  std::string ret = "";
  while (n) ret += (n & 1) ? '1' : '0', n >>= 1;
  std::reverse(ret.begin(), ret.end());
  return ret;
}

template <class T>
inline void println(T val) {
  std::cout << val << '\n';
}

template <class T>
inline void println(const std::vector<T>& vec) {
  int sz = vec.size();
  for (int i = 0; i < sz; ++i) std::cout << vec[i] << " \n"[i == sz - 1];
}

inline void Yes(bool cond) {
  println(cond ? "Yes" : "No");
}

inline void YES(bool cond) {
  println(cond ? "YES" : "NO");
}

template <class T>
using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

template <class T, class U>
std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {
  return is >> p.first >> p.second;
}

template <class Tuple, std::size_t... Is>
void tuple_in(std::istream& is, Tuple& tp, std::index_sequence<Is...>) {
  ((is >> std::get<Is>(tp)), ...);
}

template <class... Args>
std::istream& operator>>(std::istream& is, std::tuple<Args...>& tp) {
  tuple_in(is, tp, std::index_sequence_for<Args...>{});
  return is;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k; cin >> n >> k;
  vector<int> a(n); cin >> a;

  vector<int> bv(303030, 0);
  int ie = 0;
  auto f = [](int x, int y){ return max(x, y); };
  SegmentTree seg(bv, ie, f);

  vector<int> dp(303030, 0);

  for (int i = 0; i < n; ++i) {
    int cur = a[i];
    int l = clamp(cur - k, 0, n - 1);
    int r = clamp(cur + k, 0, n - 1);
    dp[cur] = seg.get(l, r + 1) + 1;
    seg.update(cur, dp[cur]);
  }

  cout << *max_element(all(dp)) << endl;

  return 0;
}

"""

import base64
import subprocess
import zlib


exe_bin = "c%1E9eQ;aVmA_AxZN+gUIXJ<DkEmc+dm+LiPOu0rmMu9?ASYgbK!Ai7S(0OcEP17;#AX9{#+dTPC}ekNmMLXvciA0wcFJa#ot9y{#j#0ZvM?nn%ciBY*|q^G;Ufe{(m<j;=e>KS_n!5dwzIQ;<$9!Z&+ndd?!D)JymzmTAMph`O&mv9DkEPf$nCZ(d>h4gItwCzwU7nyeHFQqQ~+;Q$?54CPD?F?dKA4Dlfvui6+}xp6)h*m>3d7Gln_Tj58K*srGhqG>Cn&<wB8NnT0IlhYomH?RGv{g)nk<P&rCmk6xUNP(NZ&|-ABbR=AXJm;q^2?w3O-n8R%7z-#^jeB|Wr0BflJ`?PZjW!;P`%!0P53W8oFCXgoc-Vzg!Tiq*}|RKj_a+$KAfUAwMdmdEinsoGpiF)V-QnIGKo#sTZ?&sV&??~BV{>iO1@H78Ma2`P>ndYA)EHmtQzS9hd#RWg(F(mwbsE`h&qfIkNnU0njd-$1_K0Dp)pjX!OGPZ{99G_ZfAfqcvWzs3N!7~q=?>RnFQiqNKB13NDo;C2H$YYgxg4cfB??AMUXNSi~^veSwA_e8-re@(&b*o1}oni9jI>#xT-x|#^Wmf=KPNQuFuC<sLG_jL*3NHVe|ni3<)zOIf~A|B}r4#Xl#S?Q8{*7Zh{DPK=i&L(0hALe?+=14po^M`sxmn$?BObTK$7!_0gkk8ix*vf%mDjE_JDKQxd4*UCrz9zxfyIPP{SB9c-*_zlAO{4@6jWqk?QPJ!2ZIuOFHw%I|luT@cvak@0#S$Sb2*<j&>hxTzQe*Luuq`SMK}W;Ugl_=*Jvu6kM3SjQJQ$0LW5U)ZP>XLHE>&p<tF$?kNQ>yhEuoN*LKnJ-&>!CxjfaJvNGd%X!NL&pEx0xGfDjsbKo|^0V*mtGsR%fla-q?n5ELV$QIQNshC?G`6dR0Un;rzm3TTav&TtSsvbLi`Sm|scYXkoF4&f$eb0Oy{W^Zz?A{`qxc-sAf%ehj4H*5gCW`etq33eRi+e~xi@TrjZrAm1>QlyaQ;Lpbu=WF+MV+&Dgn$9N<<OgVZ8+>Y`(M9-VnxoiLf4Qpyce+EAPcMruz#Z?sg1$-K+t@z*lYf4o9Cx}Ll@}ZT%7U%=oXWHPm_1*1*C@0}hmTW(EjoOJ%3B;-obhihS19haWvX>{ScThE_z@Leqr$T)T)l2jsPIcv_!$*mtHSNHUD*9aDx9r%d`vG<;cUGlzEp(|QTvso`0T<oqQcb=kx><HR^j6+T>bv>xC&Q4e|M_zN)`UJ3b&~6@2KzvD*Oc%UZui!tMG*?{ACqht-_~OxK)MEsc^dr=O;e2@Kfb`mpBMNIW3y<Z}AhaS!PLo)ztvyudRn~+wwNZAwPsFxg&W<*DgaIU7dSN<`*N6F3wHMd=>II#d5o4-h@25I`<u!KU)htx;VE}=1(GzuFZ|h{4wOQxw#RU{}uA+%G_p|{~7Y=!d$n^A3`2omur*x1IVMxa!oQngFLz_=aBhVfFIn+{NTCM)9=cA`ucmpBb&qgl=<2QbdTh%-{6|gE&>fcBi38^Ol!?j@YVkEkC!SQ&DPMeYF^r(H6s&>f#BpvwntY%fBBd5O1h1A@3np79e@Iv`tPA?K>8qi4Jt^puIWMBa(GGHZ=O(wWts!=^a(%rb6$EckXi8zxG&)TwYW@?<E4)S(kIz(o(JuTy=K4r!}N!*9)5T+$sPj8FTLi^JX()@Kst)!x8FyHd#_ox%S)f^_twiRk%vs3+?>V_Fz;X>I)M14bN)T&OkLO=p-kN!KXzv+bSEo7m4VD|xjOez^jRH#IRcVc-yqswQQGmo>>m*IOq}De$bpqKvD#W#rVTS*=@?|?r~S+L^&dF1Y&#wUBKM!0cF#O=Rzi{K$!R{6wN2gyWu8nrADF`Wr?%HOxu*GveVi;m)mLx#OjVC_GqP(#hj{lssrs+eA54k$_RO96$wLpX=R-3SADg&Ce1^}<`XJ_)=KPJ|t$qCIU+{b0FXJ=KyLj&W@rAbK<BCIb+*Iv8ci%p<tqZ>V?m4OU8@x1^KB^2y$2lC|y?kaIS#UcY=SoF;KMcqI^rusSdduYNwjGy1UwLR!lSl6LpwqVeQF-7xr#4P}<pr^7sL*xDD;@SW&W%>O_t@6$k!F0{Pi6VhYOnisuQUfB^b(})?gO^WEEKutY)}3>P&84?9pL8NGd}6SLu;7*Q!|`c69^saoVwvfpF8KX1>T&P;a&i6BFhCrSp`1^_<tQdd+>~VX8W5y_d$PX7LWs;i9MWe@?EbKm?XBxQ&5e^{hzkX{g}y^7xJOEyi)Zpx!(uRWNJwuG?%#@2Vtsq7aw}vUAx29Rl8$yx?QT>k$w+-;gzQS&;#h+lO|js?oX!DL|n#8+2hs9c-r0X*a9bEFu{RmU_NJB@2+u>tobW+_x^0`OQfG<{|#wod%ZpTib+{;e~ZZEyP}1cewqCyFfdD|Hr8(l^DD2A*Su}A6Gvg<waxc#@@({M^4vG8Tf-mYV#zeqHGDcNfEDzspWDYvGjjW+Dt=<d%ujs8r9YSF5>EIQTorPzji1bm<=Lg6=!2EDV=K&(+->KuF}Z(*F35Ao^=`KOOL;NpoY<|*qOG_9Gpk-QA!)_4+AAw@3;LV0a`9;yU-gty{5%%_2^K$s#qxxPi6~e6EJf-Rb_cNNo5#+od^2`dap4}I*{^;}r!l%R0scAuV?VG^+#~CLbo@8j!-~xD8T{IveI3|rAC%($1MN8p<AaZzY`0u_YtROKX370BS@pJD`kEzo64VBFx<2wt2k+yhU-1*aInmu0$drEz2PL!U8kw{Pz(#&a1?YaR?1!0F7cl*Nro0giy3g>^QSmZ(wEfJgJlYm*${#7Nr%kiisv-~ipIYUH9J8XC#`B=h?>S$_ODFg}+1q#++Joms*jLKGOAS_|K_h$PtsHcSq;KRWTGxXDn1uFJL$@CUF8dJrhKDZfEB~q8K{!;G_mj_NmHh$5H{}LFLg9OP=}Ug<5r;Bfzc_;){0j?m75C<T4D7wL#ma5ViRUiQoqp-RJ^dc=-L=;(lwGsJ3AEP(JGyi#(0EjS_U}1YmOXtMhy5eb;d+;u2uNoG(kZX>i6>wCbADnLo<{GbkKq8ZMd1-<cNVMsY?i)D$Zrqx6TSy~h0a(|6nfJGsmPzFBk@qg85$WOO^#bz9V3a9<GSl)a;qaQC}0esm<(V}#*&yzD%kZ77qh=L5e++fBU^?eaj`EMiQL+CgQN57x7?B*3Bw7bAsQENaC9{~?!`lrqs!6i0A!7$6Eb-0XlT6UmRn=N;el{a5rwbDuWwSdzpIq-EfKLO{)gM<E-zcd6XpHz+o$sRr+{vUq4*)tCxF(%RR0hb{$`+8z}^rB{04Y_z72FE(CvV~0rWMl_)g6|*h9EcJ9l|?rDZ2qX-6FI)^>xP>s9?JEl)^2l_$`iBS@|GPHWxmwuRd)<K(twYyNa){nbn#@3dY9IraN3>TZNjH?;Q}1Uy#zgz4TYtHrm_W3?3T`5x>J$Te3!lZHuoIjbN2fo&K8yBp!{(EI~n+O75-rgm#xrp#+~JYn`&8y+k7Seqs)yw;suS*5wk+60)#>Hry#ZMRxH_~M5zHCgyP3Y(~Wt$BylexFroEw<eZ^&JMkM2J$ylUT=&GN09vF}GVAo+#(7O^;RZ)|QFNE^AxT+TxMxX;;-Fze@-3(F^@mpD*%x&V7|Y$oILrxhnEQQ~8@!<gmH?`6_twFM0_OOZopSAiEYwp!-}E=4Y#*yN9Y!@M5}{E~bm=V!D_vrvKN(?pxXYD!Wfr|1PPfK2FOI&<wkitD{eIcDEU(m!+3cp56CePI-1Ww~SJDzsug6*t^yj=kp1qPt%tUc2}9DmznI2a+;PGUMeWh?h@-LRo}5<Vt2#c^xlxY+qBUBvG+%I=XoimM=V<Wg-UI^nLfMwWc6P~v~uvuCijn{(0R(&QG0pHvv!`Ke3o|nx0F}k?fzdT_Pek?by7#)N$DV^TPb~v(p{AP1Et@mbRVVfQ2IWlrzovZUjqLTiTw`1(%O!WTO1Aj1L?S!cHHb-<!oB9GA(nihg~hsrshTk{e5hg!DzLV_@x$qgXt@Yml3ffZZ6DgEnZ%j&sw~qFz>Z^Wnn&OaZ6zyY4HVx`KraM3iDcvFD$HYEnZEUO5%%%y~OyH5i4<&#BGKBLW|qUcuBmb5I>;B7n36;@k_{ve&Ne_ZDC*1;!6tqkrrQCay^v6uE6#WEe@;RQ3@~q&a1_j&BJgTF_Ta8dK~u?6ZmtQ?%UT;yww07kZsvX8}&~Q#lK7OBh=4#QvBD{4tqYZaGBGx{AFb9YDb}cm@2r^?X2MxJ4ftV{1S>gYP9%u6d%#yw{l9oqq=(Ukn#EBm85od>+C!%%g-NoqxL^5%P%Ie67#2&{6EPJn?FB)B-@!kfA-7rwe#A4nBw|&9+&ORpKqKApQ&}EPB*Xil;Q8a^XH+(gsm*DFSe~*YAPL{&}x9kOr_&YP7;(auJ?`f!Tq>_owu+(rn-6i_In2MUl`za=<nCS4*R{8ZD$i^l%K!P+)!59&TR(x-3IvHGNr#P&Wznb4I9Xh8{n04JLm7W-!4=9qaWWF%1XzLyjrHr2mQGJME*VgGBSR(7Js8m!S(hJ8?^Hr?e7V?z9JM~WG*f5G{Al4(s43D1NkwtQtxJ3$R3lDxpbV&a|U*PWKi#$2KWaCc8o52g?rYyT&k;7fApSaye0MZ$D&c6;Pc)jN1|LnNC{WDfYiz@5zz-Zms=3JdwhL;cMF~U>pJ@U>(^l<(1p}jD_6(A!@}CY`gTu15K`#@!LNj`U<^&5MG&HiXgn&CP*O~Z>A^u~h!lg41aVjhVQ^832tqg^Y>6cXf-xa1CXy*3m>wme#PCQgB1Xc_n^(JAN(*5OO;iXblff|oI*=SAgUR4<L<pychcV1X#R=FHji?}W_ISFWkL$eH4`J=Pe!<66koWcw!F%^QPnW*~$~4MhEg;A36#THhv$NONC-iyR13s`C0q+Hg;9oDtB*levDiSsfY-(#$2k~4myh$gn2`ZvxG)(A^kJ8fD5l$t9p&(dN$AjsGRPj&Rc6je{CL@E+l3`g&Y*bO+)vSq~(su|W!1Vr#ZyVM(MH`z{G=gP)T^(%jS<u(K?!xG?0Tu>QDV8rCJf_!{!@5GLv^-l%2BWpLsUo-vQFS^yzbjf#6O{&fG;mB+H!hJvtX;_#76Z?8PA(BOXc!q-B7jd@8F8k@hQ;6jP%){{A(o5A!Q=>W#uH-13GP@S2DeadOFZoyNJnGg711z}xuIZch&aPzaj>UQF{zYn1>Z&!aSbCtSuzp}q9DzU#6+wTh6J<DEeXiL9D{G!SI%TYUbN205ZyqA!pR~B)<Yp7G8&4Eh=M5h-&x!Z6dNoLbq0r{A;`!EVFD2+>}$B$mU>$J!3pn6@KIK{moSJcXNlAC`2Mes3Dd`IJ9P5;<E2Zd&(5)o)?Yv$e}6ia&nK8ZJMS{uKyh}jqd$JGBg!2P(`V;mMjI%_<1eSuXZJ05o>9kYv-5M|9IZQN>-~2hQSM+0`W0Hr&PA;KCLMi%D0e!HXXkN7Szs26Q`GnWL8ADS>9cb?qwJnZ??2Z6N2z{0<=Oe3QMLZ1CG>X?b<BG4o{v#>AI6e?{3V?}yDwn$h)&+FqfhDd*}VdzdVg7T^jV!gJC88huDb`(9aG8Q>Gaw8fzbszd42!?k!aU1J8v<%SU2GuI{kmq=^Oq3gi-yk>h#(D2%|f7_3Qolx=x?nqcGa4lh?1GcZm|8$?h+U|Bs>YdVlN3?*pR5=`wwGPHwrfbbIyspAl^gaPj|LX#J}FL#@Z!^)&61{+_sdxx(+hK>c6o^b6-PO4vHn>$7B{7sG}2Q~f%s-=^EY+I0GroKnC3Vw34N>hMzc|E2yZg{S%rw88isx{1u+KNhIku1+I#<FD5J^OJu5)EMY*U!hRDPC>8#ztx}$Cj"

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Wrong Answer

Solution code:
# N: 処理する区間の長さ
n,k = map(int,input().split())
N = 300000

INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = max(data[2*i-1], data[2*i])
  #     print(data)

# 区間[l, r)内の最大値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(n):
    a = int(input())
    update(max(0,a-k),min(N+1,a+k+1),1)
print(max(data))

Submission status: Wrong Answer

Solution code:
n, k = (input()).split()
k = int(k) + 1
m = 1
f = int(input())
n = int(n) - 1
b = 0
for i in range(n):
    s = int(input())
    if abs(f - s) < k:
        m += 1
        f = s
print(m)

Submission status: Wrong Answer

Solution code:
n, k = (input()).split()
k = int(k) + 1
m = 1
f = int(input())
n = int(n) - 1

for i in range(n):
    s = int(input())
    if abs(f - s) < k:
        m += 1
    
    f = s
print(m)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(input()) for i in range(n)]
subs=[[] for i in range(n)]

idx=0
for ai in a:
  flg=True
  for i in range(idx+1):
    if len(subs[i])==0:
      if flg:
        subs[i].append(ai)
        idx+=1
      break
    else:
      if abs(subs[i][-1]-ai)<=k:
        subs[i].append(ai)
        flg=False

ans=0
for i in range(idx):
  #print(subs[i])
  ans=max(ans,len(subs[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(input()) for i in range(n)]
subs=[[] for i in range(n)]

idx=0
for ai in a:
  for i in range(idx+1):
    if len(subs[i])==0:
      subs[i].append(ai)
      idx+=1
      break
    else:
      if abs(subs[i][-1]-ai)<=k:
        subs[i].append(ai)
        break

ans=0
for i in range(idx):
  #print(subs[i])
  ans=max(ans,len(subs[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
import typing
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
# import numpy as np

# sys.setrecursionlimit(10000001)
INF = 10 ** 16
# MOD = 10 ** 9 + 7
MOD = 998244353


def ni(): return int(sys.stdin.readline())
def ns(): return map(int, sys.stdin.readline().split())
def na(): return list(map(int, sys.stdin.readline().split()))


# ===CODE===

# https://github.com/not522/ac-library-python#install


def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x


class SegTree:
    def __init__(self,
                 # segtreeで実行したい関数
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 # モノイド：op関数に入れたとしても絶対に相手側の値が変わらないことが保証されるような値(足し算なら0、maxなら-INFなど)
                 e: typing.Any,
                 # segtreeにしたい配列を初期生成して突っ込む方式
                 v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)

        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    # st[p]にxを代入
    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    # st[p]を返す
    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    # op(st[l],...,st[r-1])を返す　l==rのときはe()を返す
    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n
        sml = self._e
        smr = self._e
        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    # prod(0,len(a))のこと　l==rのときはe()を返す
    def all_prod(self) -> typing.Any:
        return self._d[1]

    # segtree上の二分探索 leftはベース fはleftより右側にあるst[left]に対して最初に条件を見たすindexを返す
    # 条件を満たすindexがないときはlen(a)が返ってくる
    # ex. segtree.max_right(x, lambda v: v < y) + 1  idx=xより右側にある最初のst[x]<st[v]となるvを返す()
    def max_right(self, left: int,
                  f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert f(self._e)

        if left == self._n:
            return self._n

        left += self._size
        sm = self._e

        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(self._op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    # segtree上の二分探索 rightはベース fはleftより左側にあるst[right]に対して最初に条件を見たすindexを返す
    # 条件を満たすindexがないときは0が返ってくる
    # ex. segtree.max_right(x, lambda v: v < y) + 1  idx=xより右側にある最初のst[x]<st[v]となるvを返す()
    def min_left(self, right: int,
                 f: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= right <= self._n
        assert f(self._e)

        if right == 0:
            return 0

        right += self._size
        sm = self._e

        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(self._op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])


def main():
    n, k = ns()
    a = [ni() for _ in range(n)]

    dp = [0 for _ in range(3*10**5+1)]

    st = SegTree(max, -1, dp)

    for ai in a:
        cnt = st.prod(max(0, ai-k), min(ai+k+1, 3*10**5))
        st.set(ai, cnt+1)
    ans = st.all_prod()
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write('\n'.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')


def construct_sum(segtree,a,n,func=max):
    for i in range(n):
        segtree[n + i] = a[i]
    for i in range(n - 1, 0, -1):
        segtree[i] = func(segtree[2 * i], segtree[2 * i + 1])

def update(pos, x, func=max):
    pos += n-1
    segtree[pos] = x
    while (pos>1):
        pos>>=1
        segtree[pos] = func(segtree[2 * pos], segtree[2 * pos + 1])

def get(l, r, func=max):
    l += n-1
    r += n-1
    s = 0
    while (l <= r):
        if l & 1:
            s = func(segtree[l],s)
            l+=1
        if (r+1) & 1:
            s = func(segtree[r],s)
            r-=1
        l >>= 1
        r >>= 1
    return s

n,k=mdata()
a=[int(data()) for i in range(n)]
n=max(a)+1
segtree = [0]*(2*n)
construct_sum(segtree,[0]*n,n)
ans=0
for i in a:
    a1=get(max(i-k+1,0),min(i+k+1,n))+1
    update(i+1,a1)
    ans=max(ans,a1)
out(ans)