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: Runtime Error

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(30000)

@lru_cache(maxsize=30000)
def subsolve(i):
    a = As[i]
    l=None
    r=None
    for j in range(i, 0, -1):
        if a-k <= As[j-1] <= a and l==None:
            l = subsolve(j-1)+1
        if a < As[j-1] <= a+k and r==None:
            r = subsolve(j-1)+1
        if l!=None and r!=None: break
    if l==None: l=1
    if r==None: r=1
    return max(l,r)

def solve(n, k, xs):
    return max(subsolve(i) for i in range(n))

if __name__ == "__main__":
    n, k = map(int, input().split())
    *As, = [int(input()) for _ in range(n)]
    print(solve(n, k, As))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list()
b=list()
c=list()
for i in range(0,n):
    q=int(input())
    a.append(q)

b.append(a[0])
c.append(a[1])

for i in range(1,n):
    c=a[i]-a[i-1]
    c=abs(c)
    #print(c)
    if(c<=k):
        b.append(a[i])
    

for i in range(2,n):
    c=a[i]-a[i-1]
    c=abs(c)
    #print(c)
    if(c<=k):
        c.append(a[i])        
if(len(b)>len(c)):
    print(len(b))
else:
    print(len(c))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,k = map(int, input().split())
a = []
for i in range(n):
    a.append(int(input()))
a.reverse()
# dp[i] := i番目の数字から始めたときの最大値
dp = [0 for i in range(n)]
#####segfunc######
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        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 =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
#阪堺区間に注意
dp[0] = 1
update(a[0], 1)
max_a = max(a) + 1
for i in range(1,n):
    # print("{} {}".format(max(a[i]-k, 0), min(max_a, a[i]+k+1)))
    dp[i] = query(max(a[i]-k, 0), min(max_a, a[i]+k+1)) + 1
    update(a[i], dp[i])
print(max(dp))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
#####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


for i in range(n):
  x=int(input())-1
  update(x,query(max(0,x-k),min(n,x+k+1))+1)
print(seg[0])

Submission status: Runtime Error

Solution code:
def rec(pos, a, dp, n, k):
    if dp[pos] != -1:
        return dp[pos]
    for nxt in range(pos+1, n):
        if abs(a[pos]-a[nxt])<=k:
            dp[pos] = rec(nxt,a,dp,n,k)+1
            return dp[pos]
    dp[pos] = 1
    return 1
def acl_beginner_d():
    n, k = map(int, input().split())
    a = []
    for _ in range(n):
        a.append(int(input()))
    dp = [-1] * n
    ans = -float('inf')
    for i in range(n):
        ans = max(ans, rec(i, a, dp, n, k))
    print(ans)
acl_beginner_d()

Submission status: Runtime Error

Solution code:
A = []
for i in range(N):
  A.append(int(input()))
B = []
for j in range(N):
  B.append(1)

for j in range(N):
  for k in range(j):
    if (A[N-j-1] - A[N-k-1])*(A[N-j-1] - A[N-k-1]) <= K*K:
      B[N-j-1] = max(B[N-j-1], B[N-k-1] + 1)
print(max(B))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

@lru_cache(maxsize=40000)
def subsolve(i):
    a = As[i]
    l=None
    r=None
    for j in range(i, 0, -1):
        if a-k <= As[j-1] <= a and l==None:
            l = subsolve(j-1)+1
        if a < As[j-1] <= a+k and r==None:
            r = subsolve(j-1)+1
        if l!=None and r!=None: break
    if l==None: l=1
    if r==None: r=1
    return max(l,r)

def solve(n, k, xs):
    return max(subsolve(i) for i in range(n))

if __name__ == "__main__":
    n, k = map(int, input().split())
    *As, = [int(input()) for _ in range(n)]
    print(solve(n, k, As))

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
low = [0]*(10**5 * 3 + 1) #iで終わる長さ
for i in range(n):
    a = int(input())
    for j in range(max(0,a-k),a):
        low[a] = max(low[a],low[j] + 1)
    for j in range(a+1,a+k+1):
        low[a] = max(low[a],low[j] + 1)
ans = max(low)
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000007;
const long long INF = 1LL << 60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    int right = 1;
    int res = 0;
    for (int left = 0; left < N; ++left) {
        int sum = 0;
        while (right < N) {
            if (abs(A[right] - A[right-1] <= K)) ++sum;
            ++right;
        }
        res = max(res, sum);
    }
    cout << res << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()

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

ide_ele = -1

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):
        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 += 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

seg = SegTree([0]*N, segfunc, ide_ele)
for _ in range(N):
    a = int(input())
    maxi = seg.query(max(0, a-K-1), min(N, a+K+1))
    seg.update(a-1, maxi+1)
print(seg.query(0, N))

Submission status: Runtime Error

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

#####ide_ele#####
ide_ele = -1
#################

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

N, K = map(int,input().split())
Num_max = 12#3*10**5 + 1

A = [int(input()) for _ in range(N)]
st = SegTree([0 for _ in range(Num_max)], segfunc, ide_ele)

#DP = [1 for _ in range(N)]
st.update(A[0], 0)  
for i in range(N):
  l = st.query(max(A[i] - K, 0), min(A[i] + K+1, Num_max))
  st.update(A[i], 1 + l)  
  #print(i, A[i], l, st.tree)
#print(st.tree)

print(st.query(0, Num_max))

Submission status: Runtime Error

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################

import collections,sys,threading
sys.setrecursionlimit(10**9)
threading.stack_size(10**8)






def solve():
	n , k = map(int , input().split())
	arr = []
	for i in range(n):
		arr.append(int(input()))

	dp = [-1]*(n+1)
	def f(ind , prev):
		if ind == n:
			return 0
		if dp[ind] == -1:
			if prev == -1:
				dp[ind] =  max(f(ind + 1, arr[0]) + 1, f(ind+1 , -1))		
			else:
				a1 = 0
				a2 = 0
				if abs(prev - arr[ind]) > k:
					a1 =  f(ind +1 , prev)
				else: 
					a2 = f(ind + 1 , arr[ind]) + 1
				dp[ind] = max(a1,a2)
		return dp[ind]
	#print(arr)
	print(f(0,-1))
	#print(dp)

threading.Thread(target=solve).start()






'''
# Wrap solution for more recursion depth
#submit as python3

'''

Submission status: Runtime Error

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


def longest_subseq(n, k, a): 
    
    # Creating a list with all 0's of size equal to the length of string 
    dp = [0] * n 
      
    # Supporting list with  
    # all 0's of size 26 since  
    # the given string consists  
    # of only lower case alphabets 
    max_length = [0] * 26
  
    for i in range(n): 
  
        # Converting the ascii value to list indices 
        curr = a[i] 
        # Determining the lower bound 
        lower = max(0, curr - k) 
        # Determining the upper bound 
        upper = min(300000, curr + k) 
        # Filling the dp array with values 
        for j in range(lower, upper + 1): 
  
            dp[i] = max(dp[i], max_length[j]+1) 
        # Filling the max_length array with max 
        # length of subsequence till now 
        max_length[curr] = max(dp[i], max_length[curr]) 
  
    # return the max length of subsequence 
    return max(dp) 
  
print(longest_subseq(N, K, A))

Submission status: Runtime Error

Solution code:
N, k = map(int, input().split())
alst = [int(input()) for _ in range(N)]

INF = 0

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

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

def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

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

def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

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

ans = 0
for a in alst:
    l = max(0, a - k)
    r = min(N - 1, a + k)
    x = query(a, a + 1) + 1
    update(l, r + 1, x)
    ans = max(ans, x)
    
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
ans = [int(input())]
for _ in n:
    a = int(input())
    b = int(input())
    if a - b >= 3 or b - a >= 3:
        ans.append(b)

Submission status: Runtime Error

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

from atcoder.segtree import SegTree

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())

Submission status: Runtime Error

Solution code:
#####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

n, k = map(int, input().split())
st = SegTree([0] * 300001, segfunc, ide_ele)
for _ in range(n):
    a = int(input())
    v = st.query(a - k, a + k + 1) + 1
    st.update(a, v)
print(st.query(0, 300001))

Submission status: Runtime Error

Solution code:
import os
import sys
from io import BytesIO, IOBase

class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

def main():
    n, k = getints()
    a = []
    for _ in range(n):
        a.append(getint())
    st = SegmentTree([0] * n)
    for i in a:
        q = st.query(max(i - k, 0), min(n, i + k + 1))
        st[i] = q + 1
    print(st.query(0, n))


# region fastio


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)


def input(): return sys.stdin.readline().rstrip("\r\n")
def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint1(): return list(map(lambda x: int(x) - 1, input().split()))


# endregion


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
class SegmentTreeDual():
    def __init__(self, init, initX, unitA, g, h):
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        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())
g = lambda x, a, s: max(x, a)
# h = lambda a, b: a if b == -1 else b
h = max
unitA = 0
initX = 0
st = SegmentTreeDual(N + 1, initX, unitA, g, h)
# st = SegmentTreeDual([-inf] + [i for i in range(1, W + 1)] + [-inf] * (N - W - 1), unitX, 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())
    # print("a =", a)
    x = st.getvalue(a)
    l = max(a - K, 0)
    r = min(a + K + 1, N)
    st.operate_range(l, r, x + 1)
    # print([st.getvalue(i) for i in range(N + 1)])

print(max([st.getvalue(i) for i in range(N + 1)]))