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):
import types

_atcoder_code = """


__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

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

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x
"""

atcoder._bit = types.ModuleType('atcoder._bit')
exec(_atcoder__bit_code, atcoder._bit.__dict__)


_atcoder_segtree_code = """
import typing




class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 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 = atcoder._bit._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)

    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)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    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)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    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

    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])
"""

atcoder.segtree = types.ModuleType('atcoder.segtree')
atcoder.segtree.__dict__['atcoder'] = atcoder
atcoder.segtree.__dict__['atcoder._bit'] = atcoder._bit
exec(_atcoder_segtree_code, atcoder.segtree.__dict__)
SegTree = atcoder.segtree.SegTree

import sys
input = sys.stdin.readline
n, k = map(int,input().split())
A = [int(input()) for i in range(n)]



l = 3*10**5 + 10
S = SegTree(max, 0, l)
for i in range(n):
    S.set(A[i], S.prod(max(0, A[i]-k), min(l, A[i]+k+1)) + 1)

print(S.all_prod())

Solution (Python):
import typing
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x
    
class SegTree:
    def __init__(self,
                 op: typing.Callable[[typing.Any, typing.Any], typing.Any],
                 e: typing.Any,
                 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)

    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)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        return self._d[p + self._size]

    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)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    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

    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 op(x,y):
  return(max(x,y))
e=0
n,k=map(int,input().split())
seg=SegTree(op,e,300001)
for i in range(n):
  a=int(input())
  t=seg.prod(max(0,a-k),min(300001,a+k+1))
  seg.set(a,t+1)
print(seg.all_prod())

Solution (Python):

import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def getOverlap(a, b):
    return max(0, min(a[1], b[1]) - max(a[0], b[0]) + 1)

def connected_components(n, graph):
    components, visited = [], [False] * n

    def dfs(start):
        component, stack = [], [start]

        while stack:
            start = stack[-1]

            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)

            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)

        return component

    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))

    return components

from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


for _ in range(int(input()) if not True else 1):
    
    n, k = map(int, input().split())
    a = []
    for i in range(n):
        a += [int(input())]
    st = SegmentTree([0]*400001, func=max)
    dp = [0]*n
    dp[0] = 1
    st.update(a[0], dp[0])
    for i in range(1, n):
        dp[i] = 1 + st.query(max(0,a[i]-k), min(400000,a[i]+k))
        st.update(a[i], dp[i])
    print(max(dp))

Solution (Python):
class SegmentTree:
    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
        self.range = [(-1,n)] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
            self.range[self.num + i] = (i,i)
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
            self.range[i] = (self.range[2 * i][0],self.range[2 * i + 1][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 bisect_l(self,l,r,x):
        l += self.num
        r += self.num
        Lmin = -1
        Rmin = -1
        while l<r:
            if l & 1:
                if self.tree[l] <= x and Lmin==-1:
                    Lmin = l
                l += 1
            if r & 1:
                if self.tree[r-1] <=x:
                    Rmin = r-1
            l >>= 1
            r >>= 1

        if Lmin != -1:
            pos = Lmin
            while pos<self.num:
                if self.tree[2 * pos] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            return pos-self.num
        elif Rmin != -1:
            pos = Rmin
            while pos<self.num:
                if self.tree[2 * pos] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            return pos-self.num
        else:
            return -1


N,K = map(int,input().split())
seg = SegmentTree([0]*(3*10**5+1),max,0)

for i in range(N):
    a = int(input())
    L = max(0,a-K)
    R = min(a+K+1,3*10**5+1)
    tmp = seg.query(L,R)
    seg.update(a,tmp+1)

print(seg.tree[1])

Solution (Python):


import sys
input = sys.stdin.readline


INF = 0

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [-INF for _ in range(2*self.N-1)]
    
    
    def compose(self, A):
        for k, a in enumerate(A):
            self.data[k+self.N-1] = a
        first = self.N - 1
        while first > 0:
            first = (first-1)//2
            for k in range(first, 2*first+1):
                if self.data[2*k+1] > self.data[2*k+2]:
                    self.data[k] = self.data[2*k+1]
                else:
                    self.data[k] = self.data[2*k+2]

    
    def update(self, k, a):
        self.data[k+self.N-1] = a
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1] > self.data[2*k+2]:
                self.data[k] = self.data[2*k+1]
            else:
                self.data[k] = self.data[2*k+2]

    
    
    def query_max(self, l, r):
        if l+1 == r:
            return self.data[l+self.N-1]
        L = l + self.N
        R = r + self.N
        s = -INF
        while L < R:
            if R & 1:
                R -= 1
                if s < self.data[R-1]:
                    s = self.data[R-1]
            if L & 1:
                if s < self.data[L-1]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s


def main():
    MAX = 3*10**5+5

    import sys
    input = sys.stdin.buffer.readline

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

    ST = SegmentTree(MAX)
    
    ans = 0
    for i, a in enumerate(A):
        maxscore = ST.query_max(max(a-K, 0), min(a+K+1, MAX))
        
        ans = max(maxscore+1, ans)
        ST.update(a, maxscore+1)

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SegtreeMax():
    def __init__(self, aa):
        self.inf = 10 ** 16
        self.n = n = len(aa)
        self.tree_width = tree_width = 1 << (n - 1).bit_length()
        self.tree = [-self.inf] * (tree_width * 2 - 1)
        self.tree[tree_width-1:tree_width-1+n]=aa
        for u in range(tree_width - 2, -1, -1):
            self.tree[u] = max(self.tree[u * 2 + 1], self.tree[u * 2 + 2])

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = max(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    
    def max(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return -self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.max(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.max(l, r, seg_i * 2 + 2, segM, segR)
        return max(ret0, ret1)

    
    def OverL(self, l, r, a, u=0, ul=0, ur=-1):
        if ur == -1: ur = self.tree_width
        if r <= ul or ur <= l or self.tree[u]<=a: return -1
        if ur-ul==1:return ul
        um = (ul + ur) // 2
        ret = self.OverL(l, r, a, u * 2 + 2, um, ur)
        if ret != -1: return ret
        return self.OverL(l, r, a, u * 2 + 1, ul, um)

    
    def OverR(self, l, r, a, u=0, ul=0, ur=-1):
        if ur == -1: ur = self.tree_width
        if r <= ul or ur <= l or self.tree[u] <= a: return self.n
        if ur - ul == 1: return ul
        um = (ul + ur) // 2
        ret = self.OverR(l, r, a, u * 2 + 1, ul,um)
        if ret != self.n: return ret
        return self.OverR(l, r, a, u * 2 + 2, um,ur)

mx=300005
n,k=MI()
st=SegtreeMax([0]*mx)
for _ in range(n):
    a=II()
    val=st.max(max(0,a-k),min(mx,a+k+1))
    st.update(a,val+1)
print(st.tree[0])

Solution (Python):
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

class SegmentTree():
    def __init__(self, n, op, e):
        self.n = n
        self.op = op
        self.e = e
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e] * (2 * self.size)

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def build(self, arr):
        
        for i, a in enumerate(arr):
            self.d[self.size + i] = a
        for i in range(1, self.size)[::-1]:
            self.update(i)

    def set(self, p, x):
        
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        
        return self.d[p + self.size]

    def prod(self, l, r):
        
        sml = smr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

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

    def max_right(self, l, f):
        
        
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l: return self.n

    def min_left(self, r, f):
        
        
        if r == 0: return 0
        r += self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and (r % 2): r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r: return 0

st = SegmentTree(300001, max, 0)

for i in range(N):
    a = A[i]
    l = r = 0
    v = st.prod(max(0, a - K), min(a + K + 1, 300001))
    st.set(a, max(st.get(a), v + 1))

print(st.all_prod())

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
class SegmentTreeDual():
    def __init__(self, init, initX, unitA, g, h):
        self.g = g 
        self.h = h 
        self.unitA = unitA
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [initX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [initX] * self.n + init + [initX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
    
    def check(self, randX, randA, maxs, rep):
        from random import randrange
        for _ in range(rep):
            x = randX()
            a = randA()
            b = randA()
            c = randA()
            s = randrange(1, maxs + 1)
            err = 0
            if not h(a, unitA) == h(unitA, a) == a:
                err = 1
                print("!!!!! unitA Error !!!!!")
                print("unitA =", unitA)
                print("a =", a)
                print("f(a, unitA) =", f(a, unitA))
                print("f(unitA, a) =", f(unitA, a))
                
            if not h(h(a, b), c) == h(a, h(b, c)):
                err = 1
                print("!!!!! Associativity Error A !!!!!")
                print("a, b, c, h(a, b), h(b, c) =", a, b, c, h(a, b), h(b, c))
                print("h(h(a, b), c) =", h(h(a, b), c))
                print("h(a, h(b, c)) =", h(a, h(b, c)))
            
            if not g(x, unitA, s) == x:
                err = 1
                print("!!!!! Identity Error !!!!!")
                print("unitA, x, s =", unitA, x, s)
                print("g(x, unitA, s) =", g(x, unitA, s))
            
            if not g(g(x, a, s), b, s) == g(x, h(a, b), s):
                err = 1
                print("!!!!! Act Error !!!!!")
                print("x, a, b, s, g(x, a, s), h(a, b) =", x, a, b, s, g(x, a, s), h(a, b))
                print("g(g(x, a, s), b, s) =", g(g(x, a, s), b, s))
                print("g(x, h(a, b), s)    =", g(x, h(a, b), s))
            
            if err:
                break
                assert h(a, unitA) == h(unitA, a) == a
                assert h(h(a, b), c) == h(a, h(b, c))
                assert g(x, unitA, s) == x
                assert g(g(x, a, s), b, s) == g(x, h(a, b), s)
        else:
            pass
            print("Monoid Check OK!")
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")

N, K = map(int, input().split())
M = 300300
g = lambda x, a, s: max(x, a)

h = max
unitA = 0
initX = 0
st = SegmentTreeDual(M, initX, unitA, g, h)


if False:
    from random import randrange
    randX = lambda: randrange(11)
    randA = lambda: randrange(20)
    maxs = 10
    rep = 1000
    st.check(randX, randA, maxs, rep)

for _ in range(N):
    a = int(input())
    
    x = st.getvalue(a)
    l = max(a - K, 0)
    r = min(a + K + 1, M)
    st.operate_range(l, r, x + 1)
    

print(max([st.getvalue(i) for i in range(M)]))

Solution (Python):
N,K=map(int,input().split())
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[0]*(2*self.N0)
        self.orig=[0]*N
    def update(self,i,x):
        self.orig[i]=x
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
X=300000
s=SegTreeMax(X+1)
A=[int(input()) for i in range(N)]
for a in A:
    s.update(a,max(s.max(max(0,a-K),min(X,a+K)+1)+1,s.orig[a]))
print(s.max(0,X+1))

Solution (Python):
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]

def seg_function(x,y): 
    return max(x,y)

seg_el=1<<((300000).bit_length()) 
SEG=[0]*(2*seg_el) 

def update(n,x,seg_el): 
    i=n+seg_el
    SEG[i]=max(SEG[i],x)
    i>>=1 
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): 
    L=l+seg_el
    R=r+seg_el
    ANS=0

    while L<R:
        if L & 1:
            ANS=seg_function(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=seg_function(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

for a in A:
    MAX=getvalues(max(0,a-K),min(300001,a+K+1))
    update(a,MAX+1,seg_el)
print(SEG[1])

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class SegmentTree:
    def __init__(self, N, arr=None, op=None, unit=None):
        """
        INPUT
        N: 配列のサイズ
        segment tree: 1-indexedで構築
        original array: 0-indexed
                 1
           2           3
         4    5     6     7
        8 9 10 11 12 13 14 15
        ---------------------
        0 1 2  3  4  5  6  7
        """
        self.N = N
        self.unit = unit
        self.op = op
        self.tree = [unit] * (2 * N + 1)
        if arr is not None:
            self._build(arr)

    def _build(self, arr):
        op = self.op
        N = self.N
        for i, a in enumerate(arr, N):
            self.tree[i] = a
        for i in reversed(range(1, N)):
            self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1])

    def show(self):
        for i in range(self.N):
            print(self.tree[i+self.N], end=" ")
        print()

    def update(self, i, x):
        """
        arr[i]の値をxに変更する
        i: 0-indexed
        """
        i += self.N
        op = self.op
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1])

    def query(self, L, R):
        """
        L,R: 0-indexed
        半開区間[L,R)の累積演算した値を返す
        """
        op = self.op
        res = self.unit
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                res = op(res, self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                res = op(res, self.tree[R])
            L >>= 1
            R >>= 1
        return res


def op(a, b):
    return max(a, b)


unit = 0

U = 300000
N, K = map(int, input().split())
seg = SegmentTree(U+5, [0] * (U+5), op, unit)

for _ in range(N):
    a = int(input())
    l = max(0, a - K)
    r = min(U, a + K)
    val = seg.query(l, r + 1) + 1
    seg.update(a, val)

print(seg.tree[1])