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 .

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

class Segtree:
    def __init__(self, A, ide_ele, segfunc):
        self.n = len(A)
        self.size = 2 ** (self.n - 1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.data = [ide_ele] * self.size + A + [ide_ele] * (self.size - self.n)
        for i in range(self.size - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def update(self, k, x):
        k += self.size
        self.data[k] = max(x, self.data[k])
        while k:
            k = k >> 1
            self.data[k] = self.segfunc(self.data[2 * k], self.data[2 * k + 1])

    def query(self, l, r):
        L, R = l + self.size, r + self.size
        s = self.ide_ele
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.data[R])
            if L & 1:
                s = self.segfunc(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

n,k=LI()
seg=Segtree([0]*300010, -INF, max)
for _ in range(n):
    v=I()
    m=seg.query(max(v-k,0),min(300001,v+k+1))+1
    seg.update(v,m)

print(seg.query(0,300002))

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = [int(input()) for _ in range(N)]
class SegTree:
  def segfunc(self, x, y):
    return max(x, y)
  def __init__(self, n, ide_ele, init_val):
    
    self.ide_ele = ide_ele
    
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

mx = max(a)
seg = SegTree(mx + 1, 0, [0] * (mx + 1))
for x in a:
  q = seg.query(max(0, x - K), min(mx, x + K) + 1)
  seg.update(x, q + 1)
print(seg.query(0, mx + 1))

Solution (Python):

class SegTree:
    op = max
    e = 0
    
    def __init__(self, N, init=None):
        self.N = N
        self.T = [self.e]*(2*N)
        if init is not None:
            assert len(init) == N
            for i, val in enumerate(init, N):
                self.T[i] = val
            for i in range(N-1, 0, -1):
                self.T[i] = self.op(self.T[i<<1], self.T[i<<1|1])

    def get(self, l, r):
        l += self.N; r += self.N
        ret = self.e
        while l < r:
            if l & 1:
                ret = self.op(ret, self.T[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.op(ret, self.T[r])
            l >>= 1; r >>= 1
        return ret

    def __setitem__(self, i, val):
        i += self.N
        self.T[i] = val
        while i>1:
            i >>= 1
            self.T[i] = self.op(self.T[i<<1], self.T[i<<1|1])


import sys
N,K, *A = map(int, open(0).read().split())

MAX = 300_001
S = SegTree(MAX)

for a in A:
    l = max(0, a-K)
    r = min(MAX, a+K+1)
    x = S.get(l, r)+1
    S[a] = x

print(S.get(0,MAX))

Solution (Python):






code_segtree = r"""




// >>> AtCoder >>>












namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {

    unsigned long index;
    _BitScanForward(&index, n);
    return index;

    return __builtin_ctz(n);

}

}  // namespace internal

}  // namespace atcoder





namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder



// <<< AtCoder <<<

using namespace std;
using namespace atcoder;


struct AutoDecrefPtr{
    PyObject* p;
    AutoDecrefPtr(PyObject* _p) : p(_p) {};
    AutoDecrefPtr(const AutoDecrefPtr& rhs) : p(rhs.p) { Py_INCREF(p); };
    ~AutoDecrefPtr(){ Py_DECREF(p); }
    AutoDecrefPtr &operator=(const AutoDecrefPtr& rhs){
        Py_DECREF(p);
        p = rhs.p;
        Py_INCREF(p);
        return *this;
    }
};

static PyObject* segtree_op_py;
static AutoDecrefPtr segtree_op(AutoDecrefPtr a, AutoDecrefPtr b){
    auto tmp = PyObject_CallFunctionObjArgs(segtree_op_py, a.p, b.p, NULL);
    return AutoDecrefPtr(tmp);
}
static PyObject* segtree_e_py;
static AutoDecrefPtr segtree_e(){
    Py_INCREF(segtree_e_py);
    return AutoDecrefPtr(segtree_e_py);
}
static PyObject* segtree_f_py;
static bool segtree_f(AutoDecrefPtr x){
    PyObject* pyfunc_res = PyObject_CallFunctionObjArgs(segtree_f_py, x.p, NULL);
    int res = PyObject_IsTrue(pyfunc_res);
    if(res == -1) PyErr_Format(PyExc_ValueError, "error in SegTree f");
    return (bool)res;
}
struct SegTree{
    PyObject_HEAD
    segtree<AutoDecrefPtr, segtree_op, segtree_e>* seg;
    PyObject* op;
    PyObject* e;
    int n;
};

extern PyTypeObject SegTreeType;

static void SegTree_dealloc(SegTree* self){
    delete self->seg;
    Py_DECREF(self->op);
    Py_DECREF(self->e);
    Py_TYPE(self)->tp_free((PyObject*)self);
}
static PyObject* SegTree_new(PyTypeObject* type, PyObject* args, PyObject* kwds){
    SegTree* self;
    self = (SegTree*)type->tp_alloc(type, 0);
    return (PyObject*)self;
}
static inline void set_op_e(SegTree* self){
    segtree_op_py = self->op;
    segtree_e_py = self->e;
}
static int SegTree_init(SegTree* self, PyObject* args){
    if(Py_SIZE(args) != 3){
        self->op = Py_None;  // 何か入れておかないとヤバいことになる
        Py_INCREF(Py_None);
        self->e = Py_None;
        Py_INCREF(Py_None);
        PyErr_Format(PyExc_TypeError, "SegTree constructor expected 3 arguments (op, e, n), got %d", Py_SIZE(args));
        return -1;
    }
    PyObject* arg;
    if(!PyArg_ParseTuple(args, "OOO", &self->op, &self->e, &arg)) return -1;
    Py_INCREF(self->op);
    Py_INCREF(self->e);
    set_op_e(self);
    if(PyLong_Check(arg)){
        int n = (int)PyLong_AsLong(arg);
        if(PyErr_Occurred()) return -1;
        if(n < 0 || n > (int)1e8) {
            PyErr_Format(PyExc_ValueError, "constraint error in SegTree constructor (got %d)", n);
            return -1;
        }
        self->seg = new segtree<AutoDecrefPtr, segtree_op, segtree_e>(n);
        self->n = n;
    }else{
        PyObject *iterator = PyObject_GetIter(arg);
        if(iterator==NULL) return -1;
        PyObject *item;
        vector<AutoDecrefPtr> vec;
        if(Py_TYPE(arg)->tp_as_sequence != NULL) vec.reserve((int)Py_SIZE(arg));
        while(item = PyIter_Next(iterator)) {
            vec.push_back(item);
        }
        Py_DECREF(iterator);
        if (PyErr_Occurred()) return -1;
        self->seg = new segtree<AutoDecrefPtr, segtree_op, segtree_e>(vec);
        self->n = (int)vec.size();
    }
    return 0;
}
static PyObject* SegTree_set(SegTree* self, PyObject* args){
    long p;
    PyObject* x;
    PARSE_ARGS("lO", &p, &x);
    if(p < 0 || p >= self->n){
        PyErr_Format(PyExc_IndexError, "SegTree set index out of range (size=%d, index=%d)", self->n, p);
        return (PyObject*)NULL;
    }
    Py_INCREF(x);
    set_op_e(self);
    self->seg->set((int)p, AutoDecrefPtr(x));
    Py_RETURN_NONE;
}
static PyObject* SegTree_get(SegTree* self, PyObject* args){
    long p;
    PARSE_ARGS("l", &p);
    if(p < 0 || p >= self->n){
        PyErr_Format(PyExc_IndexError, "SegTree get index out of range (size=%d, index=%d)", self->n, p);
        return (PyObject*)NULL;
    }
    PyObject* res = self->seg->get((int)p).p;
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_prod(SegTree* self, PyObject* args){
    long l, r;
    PARSE_ARGS("ll", &l, &r);
    set_op_e(self);
    auto res = self->seg->prod((int)l, (int)r).p;
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_all_prod(SegTree* self, PyObject* args){
    PyObject* res = self->seg->all_prod().p;
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_max_right(SegTree* self, PyObject* args){
    long l;
    PARSE_ARGS("lO", &l, &segtree_f_py);
    if(l < 0 || l > self->n){
        PyErr_Format(PyExc_IndexError, "SegTree max_right index out of range (size=%d, l=%d)", self->n, l);
        return (PyObject*)NULL;
    }
    set_op_e(self);
    int res = self->seg->max_right<segtree_f>((int)l);
    return Py_BuildValue("l", res);
}
static PyObject* SegTree_min_left(SegTree* self, PyObject* args){
    long r;
    PARSE_ARGS("lO", &r, &segtree_f_py);
    if(r < 0 || r > self->n){
        PyErr_Format(PyExc_IndexError, "SegTree max_right index out of range (size=%d, r=%d)", self->n, r);
        return (PyObject*)NULL;
    }
    set_op_e(self);
    int res = self->seg->min_left<segtree_f>((int)r);
    return Py_BuildValue("l", res);
}
static PyObject* SegTree_to_list(SegTree* self){
    PyObject* list = PyList_New(self->n);
    for(int i=0; i<self->n; i++){
        PyObject* val = self->seg->get(i).p;
        Py_INCREF(val);
        PyList_SET_ITEM(list, i, val);
    }
    return list;
}
static PyObject* SegTree_repr(PyObject* self){
    PyObject* list = SegTree_to_list((SegTree*)self);
    PyObject* res = PyUnicode_FromFormat("SegTree(%R)", list);
    Py_ReprLeave(self);
    Py_DECREF(list);
    return res;
}

static PyMethodDef SegTree_methods[] = {
    {"set", (PyCFunction)SegTree_set, METH_VARARGS, "Set item"},
    {"get", (PyCFunction)SegTree_get, METH_VARARGS, "Get item"},
    {"prod", (PyCFunction)SegTree_prod, METH_VARARGS, "Get item"},
    {"all_prod", (PyCFunction)SegTree_all_prod, METH_VARARGS, "Get item"},
    {"max_right", (PyCFunction)SegTree_max_right, METH_VARARGS, "Binary search on segtree"},
    {"min_left", (PyCFunction)SegTree_min_left, METH_VARARGS, "Binary search on segtree"},
    {"to_list", (PyCFunction)SegTree_to_list, METH_VARARGS, "Convert to list"},
    {NULL}  /* Sentinel */
};
PyTypeObject SegTreeType = {
    PyObject_HEAD_INIT(NULL)
    "atcoder.SegTree",                  /*tp_name*/
    sizeof(SegTree),                    /*tp_basicsize*/
    0,                                  /*tp_itemsize*/
    (destructor)SegTree_dealloc,        /*tp_dealloc*/
    0,                                  /*tp_print*/
    0,                                  /*tp_getattr*/
    0,                                  /*tp_setattr*/
    0,                                  /*reserved*/
    SegTree_repr,                       /*tp_repr*/
    0,                                  /*tp_as_number*/
    0,                                  /*tp_as_sequence*/
    0,                                  /*tp_as_mapping*/
    0,                                  /*tp_hash*/
    0,                                  /*tp_call*/
    0,                                  /*tp_str*/
    0,                                  /*tp_getattro*/
    0,                                  /*tp_setattro*/
    0,                                  /*tp_as_buffer*/
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
    0,                                  /*tp_doc*/
    0,                                  /*tp_traverse*/
    0,                                  /*tp_clear*/
    0,                                  /*tp_richcompare*/
    0,                                  /*tp_weaklistoffset*/
    0,                                  /*tp_iter*/
    0,                                  /*tp_iternext*/
    SegTree_methods,                    /*tp_methods*/
    0,                                  /*tp_members*/
    0,                                  /*tp_getset*/
    0,                                  /*tp_base*/
    0,                                  /*tp_dict*/
    0,                                  /*tp_descr_get*/
    0,                                  /*tp_descr_set*/
    0,                                  /*tp_dictoffset*/
    (initproc)SegTree_init,             /*tp_init*/
    0,                                  /*tp_alloc*/
    SegTree_new,                        /*tp_new*/
    0,                                  /*tp_free*/
    0,                                  /*tp_is_gc*/
    0,                                  /*tp_bases*/
    0,                                  /*tp_mro*/
    0,                                  /*tp_cache*/
    0,                                  /*tp_subclasses*/
    0,                                  /*tp_weaklist*/
    0,                                  /*tp_del*/
    0,                                  /*tp_version_tag*/
    0,                                  /*tp_finalize*/
};

static PyModuleDef atcodermodule = {
    PyModuleDef_HEAD_INIT,
    "atcoder",
    NULL,
    -1,
};

PyMODINIT_FUNC PyInit_atcoder(void)
{
    PyObject* m;
    if(PyType_Ready(&SegTreeType) < 0) return NULL;

    m = PyModule_Create(&atcodermodule);
    if(m == NULL) return NULL;

    Py_INCREF(&SegTreeType);
    if (PyModule_AddObject(m, "SegTree", (PyObject*)&SegTreeType) < 0) {
        Py_DECREF(&SegTreeType);
        Py_DECREF(m);
        return NULL;
    }

    return m;
}
"""
code_setup = r"""
from distutils.core import setup, Extension
module = Extension(
    "atcoder",
    sources=["atcoder_library_wrapper.cpp"],
    extra_compile_args=["-O3", "-march=native", "-std=c++14"]
)
setup(
    name="atcoder-library",
    version="0.0.1",
    description="wrapper for atcoder library",
    ext_modules=[module]
)
"""

import os
import sys
if sys.argv[-1] == "ONLINE_JUDGE" or os.getcwd() != "/imojudge/sandbox":
    with open("atcoder_library_wrapper.cpp", "w") as f:
        f.write(code_segtree)
    with open("setup.py", "w") as f:
        f.write(code_setup)
    os.system(f"{sys.executable} setup.py build_ext --inplace")

from atcoder import SegTree


input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

op = lambda a, b: a if a > b else b
e = 0
seg = SegTree(op, e, 303030)
for a in A:
    seg.set(a, seg.prod(max(0, a-K), min(303030, a+K+1)) + 1)
ans = seg.all_prod()
print(ans)

Solution (Python):

class SegmentTree():
  def __init__(self,size,f=lambda x,y:x+y,default=0):
    self.size=pow(2,(size-1).bit_length())
    self.f=f
    self.default=default
    self.data=[default]*(self.size*2)
  def update(self,i,x):
    i+=self.size
    self.data[i]=x
    while i:
      i>>=1
      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
  
  def query(self,l,r):
    l,r=l+self.size,r+self.size
    lret,rret=self.default,self.default
    while l<r:
      if l&1:
        lret=self.f(self.data[l],lret)
        l+=1
      if r&1:
        r-=1
        rret=self.f(self.data[r],rret)
      l>>=1
      r>>=1
    return self.f(lret,rret)
  def get(self,i):
    return self.data[self.size+i]
  def add(self,i,x):
    self.update(i,self.get(i)+x)



n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
maxa=max(a)
st=SegmentTree(maxa+1,max,0)
for x in a:
  l,r=x-k,x+k+1
  l=max(0,l)
  r=min(r,maxa+1)
  tmp=st.query(l,r)
  st.update(x,tmp+1)
print(st.query(0,maxa+1))

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class SegTree:
    """
    セグメント木
    1.update: i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        
        if A:
            
            for i in range(n):
                self.tree[n2+i] = A[i]
            
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def add(self, i, x):
        self.update(i, self.get(i) + x)

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def bisearch_fore(self, l, r, x, func):
        """ 区間[l,r]で左から最初にxに対して比較の条件を満たすような値が出現する位置 """

        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if func(self.query(l, mid+1), x):
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def bisearch_back(self, l, r, x, func):
        """ 区間[l,r]で右から最初にxに対して比較の条件を満たすような値が出現する位置 """

        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if func(self.query(mid, r+1), x):
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -INF

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, K = MAP()
A = LIST(N)

M = max(A)
seg = SegTree(M+1, max, -INF, [0]*(M+1))

for a in A:
    res = seg.query(max(a-K, 0), min(a+K, M)+1) + 1
    seg.update(a, res)
ans = seg.all()
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]


class SegmentTree:
    def __init__(self, n, segfunc=min, ele=10**10):
        self.ide_ele = ele
        self.num = pow(2, (n-1).bit_length())
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc

    def init(self, init_val):
        
        for i in range(len(init_val)):
            self.seg[i+self.num-1] = init_val[i]
        
        for i in range(self.num-2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

    def get_val(self, k):
        k += self.num-1
        return self.seg[k]


n = 3*pow(10, 5)
st = SegmentTree(n + 1, segfunc=max, ele=0)
for a in A:
    c = st.query(max(0, a - K), min(n + 1, a + K+1))
    st.update(a, c + 1)
print(st.query(0, n+1))

Solution (Python):
def main():
    examD()

def examA():
    K = I()
    ans = "ACL"*K
    print(ans)
    return

def examB():
    A, B, C, D = LI()
    if (A<=D and C<=A) or A<=C<=B:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examC():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            

        def reset(self):
            self.parent = [-1] * len(self.parent)

        def find(self, x):
            
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            
            return self.find(x) == self.find(y)

        def size(self, x):
            
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            
            return self.parent[x] < 0

        def roots(self):
            
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            
            return len(self.roots())

        def all_group_members(self):
            
            return {r: self.members(r) for r in self.roots()}
    N, M = LI()
    uf = UnionFind(N)
    for _ in range(M):
        a, b = LI()
        a -= 1
        b -= 1
        uf.unite(a,b)

    ans = uf.group_count()-1
    print(ans)
    return

def examD():
    class segment_():
        def __init__(self, A, n, segfunc, ide_ele=0):
            
            self.ide_ele = ide_ele
            
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            
            for i in range(n):
                self.seg[i + self.num] = A[i]
                
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        
        def add(self, k, x=1):
            k += self.num
            self.seg[k] += x
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N, K = LI()
    A = [I()for _ in range(N)]
    num = 3 * 10 ** 5 + 10
    Seg_max = segment_([0] * num, num, lambda a, b: max(a,b))
    dp = [0]*N
    dp[0] = 1
    Seg_max.update(A[0], dp[0])
    for i in range(1,N):
        a = A[i]
        l = max(0,a-K)
        r = min(num-1,a+K)
        cur = Seg_max.query(l,r+1)
        dp[i] = cur + 1
        Seg_max.update(a,dp[i])

    ans = max(dp)
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""