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 typing import List, Any
import math
import sys
input = sys.stdin.readline

class SegmentTree:
    
    def __init__(self, array):
        self.n = len(array)
        self.array = [0 for _ in array]+array
        for i in range(self.n-1, 0, -1):
            self.array[i] = max(self.array[i<<1], self.array[i<<1|1])

    def set(self, i, v):
        p = self.n+i
        self.array[p] = v
        while p > 1:
            p >>= 1
            self.array[p] = max(self.array[p<<1], self.array[p<<1|1])

    def max(self, l, r):
        l += self.n
        r += self.n
        answer = 0
        while l < r:
            if l&1:
                answer = max(answer, self.array[l])
                l += 1
            if r&1:
                r -= 1
                answer = max(answer, self.array[r])
            l >>= 1
            r >>= 1
        return answer


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, K = read_ints()
    A = [read_int() for _ in range(N)]
    maxA = max(A)
    segment_tree = SegmentTree([0]*(maxA+1))
    for a in A:
        count = segment_tree.max(max(0, a-K), min(maxA, a+K)+1)
        segment_tree.set(a, count+1)
    return segment_tree.max(0, maxA+1)


if __name__ == '__main__':
    print(solve())

Solution (Python):
class SegmentTree:
    def __init__(self, iterable, op, e):
        n = len(iterable)
        self._op = op
        self._e = e
        self._size = n
        t = 1 << (n - 1).bit_length()
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)
        self._data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = op(self._data[i * 2 + 1], self._data[i * 2 + 2])
 
    def __getitem__(self, key):
        return self._data[self._offset + key]
 
    def __setitem__(self, key, value):
        op = self._op
        data = self._data
        i = self._offset + key
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])
 
    def query(self, start, end):
        op = self._op
        res = self._e
        l = self._offset + start
        r = self._offset + end
        while l < r:
            if l & 1 == 0:
                res = op(res, self._data[l])
            if r & 1 == 0:
                r -= 1
                res = op(res, self._data[r])
            l = l // 2
            r = r // 2
        return res
    
    def getTop(self):
        return self._data[0]
 
N,K=map(int,input().split())
A = []
for i in range(N):
  a = int(input())
  A.append(a)
 
A_MAX = 300000
dp = [0]*(A_MAX+5)
 
st = SegmentTree(dp,max,0)

for i in range(N):
  s = max(A[i]-K, 0)
  e = min(A[i]+K+1, A_MAX+1)
  st[A[i]] = st.query(s, e) + 1
print(st.getTop())

Solution (Python):



class SegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化  O(N)
    update(k, x): k番目の値をxに更新                O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す   O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(0-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num - 1 + i] = init_val[i]
        
        for i in range(self.num - 2, -1, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num - 1
        
        
        self.tree[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = self.segfunc(self.tree[2 * k + 1], self.tree[2 * k + 2])

    def query(self, left, right):

        if left >= right:
            print("left must be smaller than right")
            exit(0)

        if right > self.num:
            print("right must be smaller than self.num")
            exit(0)

        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        left += self.num - 1
        right += self.num - 1
        while left < right:
            if left & 1 == 0:
                res = self.segfunc(res, self.tree[left])
            if right & 1 == 0:
                right -= 1
                res = self.segfunc(res, self.tree[right])
            left >>= 1
            right >>= 1
        return res


MAX_NUM = 300000
n, k = map(int, input().split())

a = []
for i in range(n):
    a.append(int(input()))

dp = [0] * (MAX_NUM + 5)

segfunc = max
ide_ele = -float("inf")

st = SegmentTree(dp, segfunc, ide_ele)

for num in a:
    left = max(0, num - k)
    right = min(MAX_NUM, num + k) + 1

    st.update(num, st.query(left, right) + 1)

print(st.query(0, MAX_NUM + 1))

Solution (Python):
_N, k = map(int, input().split())
a = [int(input()) for _i in range(_N)]

n = 300002

def init_max(init_max_val):
    
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res


ide_ele_max = -1


num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

A = [0]*300002
init_max(A)

for i in range(_N):
    update_max(a[i], query_max(max(0, a[i]-k), min(300001, a[i]+k+1))+1)

print(query_max(0,300001))

Solution (Python):
from sys import stdin
read = stdin.read
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

MAX_A = 300005

class SegmentTree:
    def __init__(self, n:int, p:list, ide_ele, func):
        self.num = 1 << ((n-1).bit_length())
        self.tree = [ide_ele]*(2*self.num)
        for i in range(n):
            self.tree[i+self.num] = p[i]
        for i in range(self.num-1, 0, -1):
            self.tree[i] = func(self.tree[i << 1], self.tree[(i << 1)+1])
        self.f = func
        self.ide_ele = ide_ele

    def update(self, i, x):
        i += self.num
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.f(self.tree[i << 1], self.tree[(i << 1)+1])

    def query(self, l, r):
        ansl = ansr = self.ide_ele
        l += self.num
        r += self.num-1
        if l == r:
            return self.tree[l]
        while l < r:
            if l & 1:
                ansl = self.f(ansl, self.tree[l])
                l += 1
            if ~r & 1:
                ansr = self.f(self.tree[r], ansr)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            ansl = self.f(ansl, self.tree[l])
        return self.f(ansl, ansr)

def main():
    N, K = i_map()
    A = list(map(int, read().strip().splitlines()))
    s = SegmentTree(MAX_A, [0]*MAX_A, 0, lambda x, y : max(x,y))
    ans = 0
    for a in A:
        l, r = max(a - K, 0), min(a + K + 1, MAX_A)
        now = s.query(l, r) + 1
        s.update(a, now)
        ans = max(ans, now)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
read = stdin.read
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

MAX_A = 300005

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    N, K = i_map()
    A = list(map(int, read().strip().splitlines()))
    s = SegTree([0]*MAX_A, lambda x, y : max(x,y), 0)
    ans = 0
    for a in A:
        l, r = max(a - K, 0), min(a + K + 1, MAX_A)
        now = s.query(l, r) + 1
        s.update(a, now)
        ans = max(ans, now)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def ceil_log2(n):
    i = 0
    while (1 << i) < n:
        i += 1
    return i


class SegmentTree:
    def __init__(self, values, e, op):
        if type(values) == int:
            values = [e] * values

        self._n = len(values)
        self._ceil_log2_n = ceil_log2(self._n)
        self._size = 1 << self._ceil_log2_n

        self._e = e

        self._op = op

        self._nodes = [e] * (2 * self._size)
        for i, value in enumerate(values):
            self._nodes[self._size + i] = value

        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, index, value):
        self._nodes[self._size + index] = value
        for i in range(1, self._ceil_log2_n + 1):
            self._update((self._size + index) >> i)

    def get(self, index):
        return self._nodes[self._size + index]

    def all_prod(self):
        return self._nodes[1]

    def prod(self, left, right):
        if left == right:
            return self._e

        if left == 0 and right == self._n:
            return self.all_prod()

        left_prod = self._e
        right_prod = self._e

        left += self._size
        right += self._size

        while left < right:
            if left & 1:
                left_prod = self._op(left_prod, self._nodes[left])
                left += 1

            if right & 1:
                right -= 1
                right_prod = self._op(self._nodes[right], right_prod)

            left >>= 1
            right >>= 1

        return self._op(left_prod, right_prod)

    def _update(self, index):
        self._nodes[index] = self._op(self._nodes[2 * index], self._nodes[2 * index + 1])


def main():
    n, k = map(int, input().split())
    arr = [int(input()) for _ in range(n)]

    overall_max_len = 0
    seg = SegmentTree(3 * 10 ** 5 + 1, 0, max)

    for value in arr:
        max_len = seg.prod(max(0, value - k), min(3 * 10 ** 5 + 1, value + k + 1)) + 1
        seg.set(value, max_len)
        overall_max_len = max(overall_max_len, max_len)

    print(overall_max_len)


main()

Solution (Python):
def main(sample_file = ''):

    """ convenient functions
    
    
    
    
    
    """

    """convenient decorator
    
    
        
        
        
        
        
        
        
        
        
        
    """
    
    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product, combinations_with_replacement 
    
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):   
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    def permutations_count(n, r, MOD=None):
        ans = 1
        if MOD:            
            for i in range(r):
                ans = (ans * (n-i))%MOD
        else:
            for i in range(r):
                ans = (ans * (n-i))
        return ans
    from copy import deepcopy, copy 
    import operator
    
    from operator import itemgetter 
    
    
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd
    def gcd(a,b):
        
        
        if a<b:
            a, b = b, a
        while a%b !=0 :
            a, b = b, a%b
        return b

    
    
    
    
    
    

    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)
    def make_divisors(n, reversed=False):
        """create list of divisors
        
        Args:
            number (int): number from which list of divisors is created
            reversed (bool, optional): ascending order if False. Defaults to False.
        
        Returns:
            list: list of divisors
        """
        divisors = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n//i)
        return sorted(list(divisors),reverse=reversed)

    
    def sieve_of_eratosthenes(end, typecode="L"):
        
        

        
        import array
        import textwrap
        assert end > 1
        
        
        
        is_prime = array.array("B", (True for i in range(end)))
        
        is_prime[0] = False
        is_prime[1] = False
        
        primes = array.array(typecode)
        
        for i in range(2, end):
            if is_prime[i]:
                primes.append(i)
                for j in range(2 * i, end, i):
                    is_prime[j] = False  
        return primes

    class PrimeFactorization:
        '''初期化にO(NloglogN)/ 因数分解クエリをO(log(k))/ 素数判定クエリをO(1)
        >>> pf = PrimeFactorization(100)
        >>> pf.query(100)
        ((2, 2), (5, 2))
        
        '''
        
        
        
        
        
        
        
        def __init__(self, Num=10**6):
            from collections import defaultdict
            from math import floor
            self.Num = Num
            self.D = [-1] * (Num+1)
            for i in range(2, Num+1):
                if self.D[i] != -1:
                    continue
                self.D[i] = i
                for j in range(1, floor(Num/i)+1):
                    if self.D[j*i] != -1:
                        continue
                    else:
                        self.D[j*i] = i
        
        def query(self, k):
            ans = defaultdict(int)
            tmp = k
            while self.D[tmp] != -1:
                div = self.D[tmp]
                ans[div] += 1
                tmp = tmp//div
            return tuple(ans.items())
        
        def is_prime(self, k):
            return k == self.D[k]

    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    AtoZ = list('abcdefghijklmnopqrstuvwxyz') 
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    
    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something like:
        >>      pass
        >>  else:
        >>      do something like:
        >>      L[find_root(a)] = L[find_root(a)] + L[find_root(b)]
        >>      L[find_root(b)] = L[find_root(a)]
        >>      
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    
    
    
    class SegTree:
        """
        ref: https://qiita.com/takayg1/items/c811bd07c21923d7ec69
        init(init_val, ide_ele): 配列init_valで初期化 O(N)
        update(k, x): k番目の値をxに更新 O(logN)
        query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
        
        操作	    segfunc	        単位元
        最小値	    min(x, y)	    float('inf')
        最大値	    max(x, y)	    -float('inf')
        区間和	    x + y	        0
        区間積	    x * y	        1
        最大公約数	math.gcd(x, y)	0
        
        >>  seg = SegTree([14, 5, 9, 13], min, float('inf'))
        >>  seg.update(k, x) 
        >>  seg.query(l, r) 
        """
        def __init__(self, init_val, segfunc, ide_ele):
            """
            init_val: 配列の初期値
            segfunc: 区間にしたい操作
            ide_ele: 単位元
            n: 要素数
            num: n以上の最小の2のべき乗
            tree: セグメント木(1-index)
            """
            n = len(init_val)
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.num = 1 << (n - 1).bit_length()
            self.tree = [ide_ele] * 2 * self.num
            
            for i in range(n):
                self.tree[self.num + i] = init_val[i]
            
            for i in range(self.num - 1, 0, -1):
                self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

        def update(self, k, x):
            """
            k番目の値をxに更新
            k: index(0-index)
            x: update value
            """
            k += self.num
            self.tree[k] = x
            while k > 1:
                self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
                k >>= 1

        def query(self, l, r):
            """
            [l, r)のsegfuncしたものを得る
            l: index(0-index)
            r: index(0-index)
            """
            res = self.ide_ele
            l += self.num
            r += self.num
            while l < r:
                if l & 1:
                    res = self.segfunc(res, self.tree[l])
                    l += 1
                if r & 1:
                    res = self.segfunc(res, self.tree[r - 1])
                l >>= 1
                r >>= 1
            return res

    
    
    
    
    
    
    
    

    def BellmanFord(N, M, ABC, vertex_start, vertex_end, value_if_inf = -1, find_shortest = False):
        """to calculate furthest or shortest length between vertex_start and vertex_end using BellmanFord algorithm
        
        Args:
            N (int): number of vertices
            M (int): number of edges
            ABC (list): [(ai, bi, ci) for _ in range(N)] where i-th edge is directed from vertex ai to vertex bi and the length is ci 
            vertex_start (int): start vertex. usually use 0.
            vertex_end (int): end vertex. usually use N-1.
            value_if_inf (int or string as you like, optional): value you want when the furthest (or shortest) distance is infinite (or -infinite). Defaults to -1.
            find_shortest (bool, optional): choose False to find furthest path. Defaults to False.
        
        Returns:
            int or string: normally int (but can be str if you set value_if_inf to str)
            
        Example:
                N, M, P = R()
                ABC = [R() for _ in range(M)]
                ABC = [(a-1, b-1, c-P) for a, b, c in ABC]
                print(BellmanFord(N, M, ABC, 0, N-1, value_if_inf = 'inf'))

        """

        def make_reachable_list(N, M, ABC, vertex_start, vertex_end):
            reachable_to_direct = defaultdict(list)
            reachable_from_direct = defaultdict(list)
            reachable_from_start = [False] * N
            reachable_to_end = [False] * N
            reachable_from_start[vertex_start] = True
            reachable_to_end[vertex_end] = True
            reachable_from_both_sides = [False] * N
            dfs_from_start = []
            dfs_to_end = []
            for a, b, c in ABC:
                reachable_to_direct[a].append(b)
                reachable_from_direct[b].append(a)
                if a == vertex_start:
                    dfs_from_start.append(b)
                    reachable_from_start[b] = True
                if b == vertex_end:
                    dfs_to_end.append(a)
                    reachable_to_end[a] = True
            while dfs_from_start:
                v = dfs_from_start.pop()
                for i in reachable_to_direct[v]:
                    if not reachable_from_start[i]:
                        reachable_from_start[i] = True
                        dfs_from_start.append(i)
            while dfs_to_end:
                v = dfs_to_end.pop()
                for i in reachable_from_direct[v]:
                    if not reachable_to_end[i]:
                        reachable_to_end[i] = True
                        dfs_to_end.append(i)
            for i in range(N):
                reachable_from_both_sides[i] = reachable_from_start[i] and reachable_to_end[i]
            return reachable_from_both_sides
        
        reachable_from_both_sides = make_reachable_list(N, M, ABC, vertex_start, vertex_end)
        
        if find_shortest:
            dist = [INF for i in range(N)]
        else:
            dist = [-INF for i in range(N)]
        
        dist[vertex_start] = 0
        for i in range(N):
            updated = False
            for a, b, c in ABC:
                if not reachable_from_both_sides[a]:
                    continue
                elif find_shortest:
                    update_condition = dist[a] + c < dist[b]
                else:
                    update_condition = dist[a] + c > dist[b]
                if dist[a] != INF and update_condition:
                    dist[b] = dist[a] + c
                    updated = True
                    if i == N-1:
                        return value_if_inf
            if not updated:
                break
        return dist[vertex_end]

    
    def warshall_floyd(number_vertex, XYD, shift_one_for_vertex=False):
        
        
        
        
        
        
        d = [[float("inf")]*number_vertex for i in range(number_vertex)]
        for x, y, dist in XYD:
            if shift_one_for_vertex:
                x = x - 1
                y = y - 1
            d[x][y] = dist
            d[y][x] = dist
        for i in range(number_vertex):
            d[i][i] = 0 
        for k in range(number_vertex):
            for i in range(number_vertex):
                for j in range(number_vertex):
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j])
        return d


    """ initialize variables and set inputs
    
        
        
            
            
    
        
        
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    r_float = lambda: float(r())
    R = lambda: list(map(int, r().split()))
    
    R_map = lambda: map(int, r().split())
    R_float = lambda: list(map(float, r().split()))
    R_tuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    
    if sample_file:
        sys.stdin = open(sample_file)
    
    
    import random
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    N, K = R()
    A = [r_int() for _ in range(N)]

    seg = SegTree([0 for _ in range(6*10**5)], max, -float('inf'))
    
    for a in A:
        p = seg.query(max(a-K, 0), a+K+1)
        seg.update(a, p+1)
    print(seg.query(0, 6*10**5))
    
    
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    https://atcoder.jp/contests/abc173/submissions/14966961
    for i in range(1<<h):
	    if (i >> x) & 1:
            hoge
    (1 >> x) & 1 でNビット目のビット値を取得している
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()