Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

1 \leq N \leq 300,000

0 \leq A_i \leq 300,000

0 \leq K \leq 300,000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1
A_2
:
A_N

Output

Print the answer.

Sample Input 1

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

Sample Output 1

7

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

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

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



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


Sample output:
7

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class SegTree:
    def __init__(self, segfunc, e, v, init_val = None):
        """
        segfunc: function 区間にしたい操作\n
        e: Any 単位元\n
        v: int or List 要素数か格納する配列\n
        init_val: Any 初期値
        """
        self.segfunc = segfunc
        self.e = e
        self.init_val = init_val if init_val != None else e
        if isinstance(v, int):
            v = [self.init_val] * v
        self.n = len(v)
        self.log = (self.n).bit_length()
        self.size = 1 << self.log
        self.tree = [e] * 2 * self.size
        # 1-indexedなのでtree[1:self.size]がN-1要素
        # tree[self.size:self.size + N]が配列
        for i in range(self.n):
            self.tree[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1):
            self._update(i)

    def set(self, k, x) -> None:
        """
        k番目の値をxに更新\n
        k: index(0-indexed)\n
        x: update value
        """
        k += self.size
        self.tree[k] = x
        for i in range(1, self.log + 1):
            self._update(k >> i)

    def get(self, k):
        """
        a[k]を返す\n
        k: index(0-indexed)
        """
        assert 0 <= k < self.size
        return self.tree[k + self.size]

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る\n
        l: index(0-indexed)\n
        r: index(0-indexed)
        """
        res = self.e
        l += self.size
        r += self.size
        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 all_query(self):
        """
        全範囲にsegfuncしたものを得る
        """
        return self.tree[1]

    # 二分探索実装、いる？

    def _update(self, k):
        self.tree[k] = self.segfunc(self.tree[k * 2], self.tree[k * 2 + 1])

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

MAX_A = 300005

dp = SegTree(max, 0, MAX_A, 0)
for i in range(N):
    x = A[i]
    now = dp.query(max(0, x - K), min(x + K + 1, MAX_A)) + 1
    dp.set(x, now)

ans = dp.all_query()
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class SegTree:
    def __init__(self, segfunc, e, v, init_val = None):
        """
        segfunc: function 区間にしたい操作\n
        e: Any 単位元\n
        v: int or List 要素数か格納する配列\n
        init_val: Any 初期値
        """
        self.segfunc = segfunc
        self.e = e
        self.init_val = init_val if init_val != None else e
        if isinstance(v, int):
            v = [self.init_val] * v
        self.n = len(v)
        self.log = (self.n).bit_length()
        self.size = 1 << self.log
        self.tree = [e] * 2 * self.size
        # 1-indexedなのでtree[1:self.size]がN-1要素
        # tree[self.size:self.size + N]が配列
        self.tree[self.size:self.size + self.n] = v
        for i in range(self.size - 1, 0, -1):
            self._update(i)

    def set(self, k, x) -> None:
        """
        k番目の値をxに更新\n
        k: index(0-indexed)\n
        x: update value
        """
        k += self.size
        self.tree[k] = x
        for i in range(1, self.log + 1):
            self._update(k >> i)

    def get(self, k):
        """
        a[k]を返す\n
        k: index(0-indexed)
        """
        assert 0 <= k < self.size
        return self.tree[k + self.size]

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る\n
        l: index(0-indexed)\n
        r: index(0-indexed)
        """
        res = self.e
        l += self.size
        r += self.size
        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 all_query(self):
        """
        全範囲にsegfuncしたものを得る
        """
        return self.tree[1]

    # 二分探索実装、いる？

    def _update(self, k):
        self.tree[k] = self.segfunc(self.tree[k * 2], self.tree[k * 2 + 1])

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

MAX_A = 300005

dp = SegTree(max, 0, MAX_A, 0)
for i in range(N):
    x = A[i]
    now = dp.query(max(0, x - K), min(x + K + 1, MAX_A)) + 1
    dp.set(x, now)

ans = dp.all_query()
print(ans)

Submission status: Accepted

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

class segmentTree:
    def __init__(self,n,op,init_value):
        dataLen=1 << (n - 1).bit_length()
        self.data=[init_value]*(2*dataLen)
        self.op=op
        self.length=dataLen
    def getIdx(self,left,right):
        idxs=[]
        l=left
        r=right
        while True:
            idx=1
            valueL=0
            valueR=self.length-1
            while l!=valueL or valueR>=r:
                if l<=(valueR+valueL)//2:
                    valueR-=(valueR-valueL+1)//2
                    idx*=2
                else:
                    valueL+=(valueR-valueL+1)//2
                    idx=idx*2+1
            idxs.append(idx)
            if valueR==r-1:
                break
            l=valueR+1
        return idxs
    def get(self,n):
        return self.data[n+self.length]

    def set(self,n,value):
        idx1=n+self.length
        self.data[idx1]=value
        while idx1!=1:
            idx2=idx1^1
            if idx1>idx2:
                idx1,idx2=idx2,idx1
            self.data[idx1//2]=self.op(self.data[idx1],self.data[idx2])
            idx1//=2
    def query(self,l,r):
        idxs=self.getIdx(l,r)
        ret=self.data[idxs[0]]
        for idx in idxs:
            ret=self.op(ret,self.data[idx])
        return ret


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

N=300000
seg = segmentTree(N, op, 0)

for i in A:
  l=min(N,max(0,i-K))
  r=max(0,min(N,i+K))
  v=seg.query(l,r+1)
  seg.set(i,v+1)
print(seg.query(0,N))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class SegTree:
    def __init__(self, segfunc, e, v, init_val = None):
        """
        segfunc: function 区間にしたい操作\n
        e: Any 単位元\n
        v: int or List 要素数か格納する配列\n
        init_val: Any 初期値
        """
        self.segfunc = segfunc
        self.e = e
        self.init_val = init_val if init_val != None else e
        if isinstance(v, int):
            v = [self.init_val] * v
        self.n = len(v)
        self.log = (self.n).bit_length()
        self.size = 1 << self.log
        self.tree = [e] * 2 * self.size
        # 1-indexedなのでtree[1:self.size]がN-1要素
        # tree[self.size:self.size + N]が配列
        for i in range(self.n):
            self.tree[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1):
            self._update(i)

    def set(self, k, x) -> None:
        """
        k番目の値をxに更新\n
        k: index(0-indexed)\n
        x: update value
        """
        k += self.size
        self.tree[k] = x

        for i in range(1, self.log + 1):
            self._update(k >> i)

    def get(self, k):
        """
        a[k]を返す\n
        k: index(0-indexed)
        """
        assert 0 <= k < self.size
        return self.tree[k + self.size]

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る\n
        l: index(0-indexed)\n
        r: index(0-indexed)
        """
        res = self.e
        l += self.size
        r += self.size
        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 all_query(self):
        """
        全範囲にsegfuncしたものを得る
        """
        return self.tree[1]

    # 二分探索実装、いる？

    def _update(self, k):
        self.tree[k] = self.segfunc(self.tree[k * 2], self.tree[k * 2 + 1])

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]

MAX_A = 300005

dp = SegTree(max, 0, MAX_A, 0)
for i in range(N):
    x = A[i]
    now = dp.query(max(0, x - K), min(x + K + 1, MAX_A)) + 1
    dp.set(x, now)

ans = dp.all_query()
print(ans)

Submission status: Accepted

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

class segmentTree:
    def __init__(self,n,op,init_value):
        dataLen=1 << (n - 1).bit_length()
        self.data=[init_value]*(2*dataLen)
        self.op=op
        self.length=dataLen
    def getIdx(self,left,right):
        idxs=[]
        l=left
        r=right
        while True:
            idx=1
            valueL=0
            valueR=self.length-1
            while l!=valueL or valueR>=r:
                if l<=(valueR+valueL)//2:
                    valueR-=(valueR-valueL+1)//2
                    idx*=2
                else:
                    valueL+=(valueR-valueL+1)//2
                    idx=idx*2+1
            idxs.append(idx)
            if valueR==r-1:
                break
            l=valueR+1
        return idxs
    def get(self,n):
        return self.data[self.getIdx(n,n+1)[0]]

    def set(self,n,value):
        if n<0 or n>=self.length:
          return False
        idx1=self.getIdx(n,n+1)[0]
        self.data[idx1]=value
        while idx1!=1:
            idx2=idx1^1
            if idx1>idx2:
                idx1,idx2=idx2,idx1
            self.data[idx1//2]=self.op(self.data[idx1],self.data[idx2])
            idx1//=2
        return True
    def query(self,l,r):
        idxs=self.getIdx(l,r)
        ret=self.data[idxs[0]]
        for idx in idxs:
            ret=self.op(ret,self.data[idx])
        return ret


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

N=300000
seg = segmentTree(N, op, 0)

for i in A:
  l=min(N,max(0,i-K))
  r=max(0,min(N,i+K))
  v=seg.query(l,r+1)
  seg.set(i,v+1)
print(seg.query(0,N))

Submission status: Accepted

Solution code:
def resolve():
    N, K = map(int, input().split())
    n= 300010
    #####segfunc######
    def segfunc(x, y):
        return max(x, y)

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i + num - 1] = init_val[i]
            # built
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

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

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

    #####単位元######
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num

    #init([0]*300005)

    for i in range(N):
        a = int(input())
        b = query(max(0, a-K), min(a+K+1, 300001))
        update(a, b+1)
    print(query(0, 300000))
resolve()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

#####segfunc#####
def segfunc(x, y):
    return max(x,y)
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    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: セグメント木(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 main():
    N, K = MI()
    Seg = SegTree([0] * (300000+2), segfunc, ide_ele)
    
    for i in range(N):
        num = I()
        l = num - K
        r = num + K
        if l <= 0:
            l = 0
        if r >= 300000:
            r = 300000

        temp = Seg.query(l, r+1)
        Seg.update(num, temp+1)
    print(Seg.query(0, 300001))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

class SEGTree:
    def __init__(self,N,op,e):
        self.size=2**(N-1).bit_length()
        self.e=e
        self.op=op
        self.SEG=[self.e]*(self.size*2)
    
    def update(self,i,x):
        i+=self.size
        self.SEG[i]=x
        while i>0:
            i>>=1
            self.SEG[i]=self.op(self.SEG[i*2],self.SEG[i*2+1])
            
    def query(self,l,r):
        l+=self.size
        r+=self.size
        lres,rres=self.e,self.e
        
        while l<r:
            if l&1:
                lres=self.op(lres,self.SEG[l])
                l+=1
            if r&1:
                r-=1
                rres=self.op(self.SEG[r],rres)
            l>>=1
            r>>=1
        res=self.op(lres,rres)
        return res
    
    def get(self,i):
        return self.SEG[i+self.size]

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
M=max(A)
seg=SEGTree(M+1,max,0)
 
ans=0
for i in range(N):
    l=max(0,A[i]-K)
    r=min(M,A[i]+K)
    res=seg.query(l,r+1)+1
    ans=max(ans,res)
    if seg.get(A[i])<res:
        seg.update(A[i],res)
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")


# update: node[x] を更新する
# segfunc: 半開区間 [a, b) での処理
def segfunc(a, b):
    return max(a, b)


class SegmentTree:
    def __init__(self, arr, ini):
        size = len(arr)
        self.ini = ini
        self.n = 2 ** (size-1).bit_length()
        self.node = [self.ini] * (2*self.n)

        for i in range(size):
            self.node[i+self.n-1] = arr[i]
        for i in reversed(range(self.n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])
    

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2*x+1], self.node[2*x+2])
    
    
    def query(self, a, b):
        res = self.ini
        l = self.n - 1 + a
        r = self.n - 1 + (b-1)
        
        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1
        
        return res
 

# 処理内容
def main():
    N, K = map(int, input().split())
    
    seg = SegmentTree([0]*300010, 0)
    for _ in range(N):
        A = int(input())
        a = max(A-K, 0)
        b = min(A+K, 300000)
        tmp = seg.query(a, b+1) + 1
        seg.update(A, tmp)
    
    print(seg.query(0, 300000))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")


# update: node[x] を更新する
# segfunc: 半開区間 [a, b) での処理
def segfunc(a, b):
    return max(a, b)


class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])
    

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2*x+1], self.node[2*x+2])
    
    
    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b-1)
        
        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1
        
        return res
 

# 処理内容
def main():
    N, K = map(int, input().split())
    
    seg = SegmentTree([0]*300010)
    for _ in range(N):
        A = int(input())
        a = max(A-K, 0)
        b = min(A+K, 300000)
        tmp = seg.query(a, b+1) + 1
        seg.update(A, tmp)
    
    print(seg.query(0, 300000))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")


# update: node[x] を更新する
# getmin: 区間 [a, b) の最小値を返す
class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 1 << size.bit_length()
        self.n = n
        self.node = [0]*(2*n - 1)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = max(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = max(self.node[2*x+1], self.node[2*x+2])
    
    def getmax(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b-1)
        while l <= r:
            res = max(res, self.node[l])
            res = max(res, self.node[r])
            l  = l // 2
            r = r // 2 - 1
        return res
 

# 処理内容
def main():
    N, K = map(int, input().split())
    
    seg = SegmentTree([0]*300010)
    for _ in range(N):
        A = int(input())
        a = max(A-K, 0)
        b = min(A+K, 300000)
        tmp = seg.getmax(a, b+1) + 1
        seg.update(A, tmp)
    
    print(seg.getmax(0, 300000))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

using namespace std;

using int64 = long long;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

  vector<int> dp(303030, 0);

  int mn = *min_element(all(a));
  int mx = *max_element(all(a));

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

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

  return 0;
}

"""

import base64
import subprocess
import zlib


exe_bin = "c%1E9eRLbum4744vEmO&Nu1#D6%h<;FNv^-6RZ#y%a)wcR!-d5rr{$DvLweUvgAsm#9=9<bqq|6LfB<#`oWexdv=#@cMHoo%VBd0*fFummUferrQsusPumcQ5MsVU2w?5KGw(?=V~Mmq``_mINcY{}+<V`9_kGOF)%Cp|U%P?h2rDJzD+D>)0)=m(_#S&s1h6JDAHFXqmyvnE8&z_8dY02tQ?4CFugReBdU`3*QcgunN%69DiI&1ha(dX;y2})_?lPN(&d_!@mumG4RIi2VwNQCRtyGUuHa;W$bW>bU-9$@`ly)8$gIND)k;3b#k7y~=`x@xYBY$|YQo4z@SIjR*X@41I^Kfk>+`Fdn+DLF^Bpgi+tsH7vvvN(NJrT2CC-=!pW!G=$k>zo|4XQp@Qw*>F^5%i(e)H4UKYDn9`0`=rRK=0qmtTaki%EXo(8C;PE~YlB_g1zg9xY=g=afnKEG&S(T?GFzG_<?`{*5B?Jw@<uafR`{Mexxg_*+HnUsgmuQUt%U2yQBZ-%+I9WrXbrZRsjv=VwK5YY{s)6v2O1q(3)+{RLzxX|X9<R=P0%fhhPLS15Q5Td=TR6JjuM%{912*APM2IuMHr3DF-H1%U|O?hYXsiifs_6JjXd-O(0_MMK^G-bhHfR`|*-8@j^rglAJ&uErt>57xTG#!xgE@dmm?ha=GMj|*bl9~KkdfXA~5uvNYOL^vSC5@I~$AMkby-3@}LYmFeQt_p;svNf?O97_lw8fx@L!=l^a*(M7(t``KcKOWl-*MfpS5{U)yLNL;~O{eEro!Ai#2;0MAKMXV&j(K`<+(SdcU?`r5Mg5VmxI@_10BX_g1BDuGV~sWjVo4EwxHS+E66it)5qhHA!_lCyDU?VKgz#d3`4-$7xKjx9-zoI@!w~@di9`q-O}W63U+{~ep|D5>LIZ)p9Te*eW1sE<#|mhT&dz`zJhHy6O;}}bAnSeJ);8ffdt<KV$XBnkuO@AqH@jNBg2TQ_fj4gky+(qkj{!~`<=aSWrSO?2pG#%(X{1OY&%vLE%dgkYt9MkO)EHe)9LV?5>n-r94u`Ao&h!$+9(nlDd3e$tp?vb<@O(V+j^*?X^4Z4D;a@*_XDOa^87eQ<|CI@Q^AVM2=P|p#*yyHc(BU)GV3Q7?ruTD`O^Y-B&@zSMSzDsoXGc}IMTJkR@C7P7t-{s&c1DFSQsHM+c(n?*(thFat5i7K?|7SDtisuTM|_D2@2B?5NdDf1Wl)8yZz4k~+^E8Ls&Mu5#{(){egEB~!pl_nUKMUq;g75E`6~Pg6<)5wpHkr!D*Ra$Ua7*zRJd7%zof#gDx4pF*Tj#O9$0K6{K%MS$R6T{Uo=gS?CRwJWv{A*Z_Bb4s3G5vDw*jll&daA9$lR|B=ZZAM;B+tWWF4ETw<B0WZr;0x;pc?%%7_U9$lQ-Bl901kFL$^l=*j%$L?kZW&XFwqboCa$o%WbqYE>gGJgblbX}%J=Km9UbXlfB=Jz9yuFBYCejo6Cdzc?wUw7T)$hvx5-9264ll~w-YP_lr9VEGHH#^4C6`;eX#99-dYPKu^Z%viHyF~G6+Cr~Y^3qh=fJ`6)f+MFayCz`7{Igl5+{il*Snj_H2JK6&_*Yc*NvG3Spn^2v7(+i#8Hbf=8RI}WIpgJy`J5-kT3_m_@8cXv$NDVG+}N%6eA0>Z-^_yU@ByROc`Ett3rFu+NYY0D@=7myQ@d)B_esZPyB<2-2aK{^UOGMHu9bHp50x6ZGxaC1Zet)0pLnHN@A#~tW8{ow*Xa`VV7$&r%l%z2zO(>M`cluz%{h;w$7=A)=9BKOtrM;LlzzO8-Z6rxYj~E!OEzqzfwk7eDlJ%XOCLa0zS}>GU(eynvg}?2J&?!GjXC$<drm@;v5_%8khYBc9z<NJZCT$awm*7zZG&TsAD-l7`O)rLt827!C%0dAZQuy+oRliRmpm~l)>>0HWk-(Ovyl(%AAZlk9pO`aR@MhGuk@0)9=tWlfAT;4_}e9Xs_{{tn>|@!S+-MgXoefDo^*Ck8Z900<#oO!Ro~A`FC~vF)6w<?&h7y|wG&xzyE1=MWs3F`OvhC6eVF6X63eb7I0R|TC5`ja>nAHM%gAWC%X!dk*?5p2-f#3d-$}m5ORt?Q-!tlPIcMA!-y}ag4kivK--8jFMvho^Z{pC#0dPX4M>^@MpYS+;;j#E$b8~68bIfJgIOZ97BQ?lb9+(f3Jg7Ce_MwaAe!0;f(#$7^#?#9@&JQg=8s9Z;*@aK3Zs!@xL$5-mHDz2g>Z`5xa38vy6Vk7~wHEs6Iy1qE3p)azwU4gb=XQSTviSbXH9WyR!HElo)0{7GR=F?>7d~+v{_OBs(7pSh^L=mNfW`N#;c?F6{8;jh5KHQxpfeuWI}iLVRN7MR)r1esNR>~^{X2X%RY`n-qp5GgBpw{C{4O6j<AiG+l~0e1wMvygNFH-L!4vmvXdhki*I(iU@9=((IzlRw_ixn@?$y-lf5%mxYJMHazE!xrTRwx!&eNkwn7(wf^5i0%7pwDCi|+$iOyK>qu%A-RuUTy*y$fYwoxghy>FIPM@~OLPt?7R@;C4TeUXIAf8={Gq-byb923G0lZMB<&{Hjak6UQ=g4NlDPi~YB5aoy(H;=0`>Ou&+Wg^{@k_q+Bu`5x}v)H-^cWYb5WWt<)_H^oc)Ez5Sv8(%8N1;h`Z;*uZ9Ya2IU6Yf&E*20fu#nSYBpzDF1zWeRZv)Rm(pJV4T%Yn#i+2c6ncq1J@C!a5wAIc-E`kg^`+D@4??*X#!&(LWVAeNr|6lD*9BYe`Sblo}T3!GW>#gcO>U(Ba2`x<IK2%72p;Y-<wU_<WUaf;L+`&{}}U{5}iKK-e@$4>qWem#a?PeNb5v%n_b-qO>uQuF&};8Tmw$z*j<zWSmm^BuU_x5shHD;>U_mww9+|9+;k+m|Z+0Zu}y>Pne3zX?*=#gBsSN6Pt|Y90rshfkIM2O4yq<)!1|Qn;0V!>rs&tF~mP`|QmBTPE-n&hw!EZKWf3$!6+jL7yL=E#ajZems36&rR}&XGJ*2N*&Z-B^oSdZ)fwvu>45!T7J0sttzPXV1FuM*yW&}u0nV6Foem{FvxMJE}vf?PAKOQif_sEfrP?$@zQ7f=)E?@?a{O7!M`*iH}BSr0PL+3`Nnbo!~N4M{RVHKaI1QzTz1XM=Ye*)q%XYE8DITz`B`K9i<0#HpWw8g5^at*m<gYB&L^F5OQ&7g>Nj~fIC$r=<U2S)s!gyb-{glA^w~vzT2Y>}-9mfBFA81B-bCn|$xt*9vIhnSNrP=&vu!Yzuw8w%OxD?=f&xYmipT)gWGs%gxPo0{bFk-wZLx6B))m@15Q>W3@la@8#|m5fSJtjg4hG>3r!E{7SJ*o0ZMWh}n61OsYy;#5TRT+nwWh9q?b>w_|3GihuZY4|{a3cAp2Io{8Q&Tb^WuNJZSIni8+f8Tf37=|%{~J3QgHpxfvx~r4NLoT*xdLOw*qccL6n07<`tk3pt}Hn6X?ra{+XS-YZKvytlTA)Wu`q`nH6!2-Hm~rYgFSYEKf)+m4E!>Y<3z2%+_{u&0kn5wwrd68!x`$&sWthXZjd3+YJ3yKR=`HZSc7R`g<h;F0*ymaBI2Q<f(9(P5C(DU7bF;<+2|xuCS3ySo@ts>4O#Q9)brk;|q94Gg}`rw3=&nm$=Qgl(E%Z_h6~Z+;HDKm$_-U%x!+0D;Y7Co0|Z0nd@53Hjo9KR<p^4519DyGy|Up;Y5_fr(ZQ&Z#OHw#xYbvyVKyG5Ye>d$+g8}TRgVaVQz^RYDa!%?*=<27`OU8CY$A&Z2}?Ba5cZEAU`*hj#rSQ#?r|OGG(fIy__7JU;6zD@{@8H>VKDG^}7{NeW(KE9;x`U2<wG%p<E~z%7t>F{QoH|-pb;uES{?VT~bXwoR;sU6&91Lp}{;B+kA!EUrKov@4bZbEH-yBr7XV7o@>~%(8sgc7}CA;VSwGq(=?dLVw7X_dM>6&c@|5op;R4X#lm94oiuL9o;jN6_}KFui+Nr|>9k3UKT)RbH`8aaPuBkBL@Ni6Qu6pX3e8f!hT6+gp7nEv@@YEoPbsgC?fzdD_PemYv{OglL}?$T+bF${(nl%%M@pZebdu6nDSeyLGnCF#2Z8^D!hQ!}Wqn)QT3cODZ!#(-ZP(jZ+Z$G{O3Iw$9!HbCp|M^;{}9_HFk4LpeyPRZV7d$9B}6QU8*}Sgi<josvlgG1TlZSLEVmxCxGA@ewD|node!3Pxpl3@D{}i=i&v6{f_N3N7MQ;hVkWkNxFvU9XmKl<E{HG4<qv4_g`}mr5Wa{U)o*+mug;xIT6}TtJksJz3hsvzI2G9Wp~Yd>+X~_N-+8t8#d9z`MvUbBtRBbn!~p(mp#Hg%;>|_yUfGtFJWl<#iQ<1p@fM2TMDgEIJM8|z(q%r8<(HBj%Wb*-VVTDj?&ktdvD3Lgi!Y-19vyx)#iw=nI!<YKNZ0OHWqj^@#i<>eZvEUN%g>$nV*P(imS0F-DX@MD$^TUD*xdE`yliLg`k9jDtLOCpD8=>tJSp3myWThh-cxHxjc#3ym*DTcbJwBCfW6G`FLtb8qDrCsgytf6#85cT<O728`Tc%~-nbtqV&@R{$51op+&)%B{^KIJ6~=o7*kQl7vg2&ni1KsKnH434?c7)dzqts0poET>u3Hu(8Ym*avj|=$_jB%f`=b)YKl=H7qNH%%$O|RPdeG1NujSw4my(^!wfM^=3a+<*v`9a{pyR!RUJOyZ%2-(5UIh0T3+KuBi^%UVD(xPk7uju6G8WF0`Ee0D&lhR;mqqXsMeGy{#tOG=a5z+<PH*^@MvP*5dLrSlNAS3>lQU7yBc!COoJVTa){y9dn!_mwotr$}-8T#EJsaA(y&E@RCeZoR*C?UgFR`%Rx3Sgb6NE&vSMVz7E0{y$YZ8QTEF2AsBoG%9VzRH#9w7OoBS9Px0+?KsAc7E#30otvUVlUgim`Y?@F#~zAT}@<35lVg{rWY|rouv)LlYMK@wk7700W5cAboNFKu8EC2L>?BM#Tx(6^*DMv~O~Cz!*2UaU8<>4LyQ~ry%d%L<INE8(baUHn^ry4r&28Zzt!6jqUASo^GMr)#~$r)ev~kPXzBqIVUM9Bom=v(Zr^f7IhNOdDEM8;+mu)dX1(D{pnd+`Zj`zn9%PBOX_?uy^t#ZN!t(i*X{98pS@sOmXaHlmv=O3a;NkI!VECIzoOd*^j*>BX623GweF5KHu)^+YtC?C_Sggqy@>>?7fv42Ys+a}fkaYXEd`U&T3S>YT)C_|ot-bs*3)FAfgVj9Q?-p-B$sPfu!s4?Go6zQWDOS03@nhqr)`Yb6FUY(e=krmuF!r~3rE4^AhAbdV#p5eSSk9qQf_NBY41&jBf*v7Ad$I#f1;n*gFB*NPoZL5xv~v>8;(Uai~!f-p@<&^X>BkfVv{f>Sha7BK?T+re9OMF$7AxQwTJrY0n#6g=Q*$*2neB}Kxj}DM0x!7{Ar-rV0CEIKM)Q;MK%Zvh}hv=!^5`F-Qtff7%#zFSuQS7B(IzmPRHZ(zd9#OpSNw($?IP)9XfsX9?NL$dGzsjp)=WRjOnxYT}JCD&f+@y*Ut?^iQzDP_Fl|r9i{mC%c=BPyanH9)VbR1{W<p@t$WYb`|oz5#9(sz^R$$`7qR{ubo5T5#B><X-p3hbiCHX9Q9u5>h~iVG&)(Y^WpO6G|Je9<QT<lRv-f*O)%q6|(BDneIqUg2AEPWD#)^LaC7nKt7ce@lleg;VBRYK+S721{FO!ZwrqgHdBaA++i-TCTEctt#K6`&)biPhrKmMN(?fzx&TZ}H$EjXJ_|KD`_#r}VySo<&N^jUm_(Y?C%_5M7l(`RuMMqN62{r-7_DEXNzewqJ&429SGTR(p%h?1wv^x1oI(`AMGtJnXKXmfz`|L;QESDhbfJ=U+ibWHj<apy9Hf9gE#f3DNdy^m4C_L*Lv6$1?n=lW0eYp8yU?)+-e>6dXz`})8p)34Xzh2sB({wam0`gOF!cptis%soHmtNN}kgY@99)crKCUq1_q=-<6kp;n!OUjKgqn*m1W"

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