Problem:


Score : 500 points

Problem Statement

You have a string S of length N.
Initially, all characters in S are 1s.

You will perform queries Q times.
In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit).
Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

1 \leq N, Q \leq 200,000

1 \leq L_i \leq R_i \leq N

1 \leq D_i \leq 9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q

Output

Print Q lines.
In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Sample Input 1

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

Sample Output 1

11222211
77772211
77333333
72333333
72311333

Sample Input 2

200000 1
123 456 7

Sample Output 2

641437905

Don't forget to take the modulo.



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


Sample output:
11222211
77772211
77333333
72333333
72311333

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
str1="1"
str2=""
for i in range(0,n):
    str2=str2[0:]+str1[0:]
for i in range(0,q):
    a,b,d=map(int,input().split())
    d1=str(d)
    for j in range(a-1,b):
        str4=str4[0:j]+d1[0:]+str4[j+1:]
    xx=int(str4)
    yy=xx%998244533
    print(yy)

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
s = "1"*n
for i in range(q-1):
  L,R,D = map(int,input().split())
  s = s[:(L-1)] + str(D)*(R-L+1) + s[(R):]
  print(s)
L,R,D = map(int,input().split())
s = s[:(L-1)] + str(D)*(R-L+1) + s[(R):]
print(int(s)%998244353)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,Q = MI()
mod = 998244353


class LazySegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,X_func,A_func,operate,X_unit,A_unit):
        self.N = N
        self.X_func = X_func
        self.A_func = A_func
        self.operate = operate
        self.X_unit = X_unit
        self.A_unit = A_unit
        self.X = [self.X_unit]*(2*self.N)
        self.A = [self.A_unit]*(2*self.N)
        self.size = [0]*(2*self.N)

    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.X[self.N+i] = init_value[i]
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1],self.size[i << 1 | 1])


    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1],self.size[i << 1 | 1])
            i >>= 1

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.X[i],self.A[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1),self.size[i << 1 | 1])
            i >>= 1

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.X[i] = self.operate(self.X[i],self.A[i],self.size[i])
        if self.A[i] != 0
            self.A[i << 1] = self.A[i]
            self.A[i << 1 | 1] = self.A[i]

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.X_unit
        vR = self.X_unit
        r = 0
        while L < R:
            if L & 1:
                vL = self.X_func(vL,self.eval_at(L),self.size[L])
                L += 1
            if R & 1:
                R -= 1
                r += self.size[R]
                vR = self.X_func(self.eval_at(R),vR,r)
            L >>= 1
            R >>= 1
        return self.X_func(vL,vR,r)
    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.A[L] = x
                L += 1
            if R & 1:
                R -= 1
                self.A[R] = x
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


def X_func(x,y,r):
    return (x*pow(10,r,mod)+y) % mod


def A_func(a,b):
    return b


def operate(x,a,r):  # 右作用
    return (a*(pow(10,r+1,mod)-1)*pow(9,mod-2,mod)) % mod


LST = LazySegTree(N,X_func,A_func,operate,0,0)
LST.build([1]*N)

print(LST.fold(0,N))
for _ in range(Q):
    l,r,d = MI()
    LST.operate_range(l-1,r,d)
    print(LST.fold(0,N))

Submission status: Runtime Error

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


#####ide_ele#####
ide_ele = 2**31 - 1
#################


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

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [None] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
        """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
        l += self.num
        r += self.num
        lm = l >> (l & -l).bit_length()
        rm = r >> (r & -r).bit_length()

        while r > l:
            if l <= lm:
                yield l
            if r <= rm:
                yield r
            r >>= 1
            l >>= 1
        while l:
            yield l
            l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = v
            self.data[2 * i + 1] = v
            self.lazy[i] = None

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = x
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res 
n, q = map(int, input().split())
D = dict()
D[0] = "1"
Seg = LazySegmentTree([0] * n, max, 0)
for i in range(1, q + 1):
    l, r, d = map(int, input().split())
    D[i] = str(d)
    Seg.update(l, r,i)
    ans = list()
    for j in range(n):
        x = min(Seg.query(0, i), Seg.query(i, -1))
        ans.append(D[x])
    print("".join(ans))

Submission status: Runtime Error

Solution code:
def yuni(n,e):
  s=n
  for i in range(e):
    s+=mod
    if s%e==0:
      return (s//e)%mod
N,Q=map(int,input().split())
mod=998244353
S="1"*N
L=[]#各桁までのmod
a=10
R=list()
for i in range(N):
  L.append(yuni(a-1,9))
  R.append(yuni(a,10))
  a*=10
  a%=mod
for i in range(Q):
  a,b,c=map(int,input().split())
  a,b=N-b+1,N-a+1
  s=L[a-2]
  if a==1:
    s=0
  t=L[b-1]
  k=L[-1]
  w=(yuni(R[b-a+1]-1,9))*pow(10,a-1,mod)*c
  qwe=(k-t+s+w)%mod
  print(qwe)
  qwe=qwe-k
  #ここからLの上書き
  L=L[:a-1]+[(s+(c*yuni(R[y+1]-1,9)*R[a-1]))%mod for y in range(b-a+1)]+[(qwe+L[b+y])%mod for y in range(N-b)]

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
_string = ""
for i in range(n):
    _string = _string + "1"

for i in range(q):
    l, r, d = map(int, input().split())
    tmp = ""
    tmp = str(d) * (r-l+1)
    _string = _string[0:l-1] + tmp + _string[r:]
    print(_string)

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
s = "1"*n
for i in range(q-1):
  L,R,D = map(int,input().split())
  s = s[:(L-1)] + str(D)*(R-L+1) + s[(R):]
  print(s)
L,R,D = map(int,input().split())
s = s[:(L-1)] + str(D)*(R-L+1) + s[(R):]
sr = int(s)%998244353
print(sr)

Submission status: Runtime Error

Solution code:
MOD = 998244353 
X, Y = 500, 400
n, q = map(int, input().split())

re = [[pow(10, X * i + j, MOD) for j in range(X)] for i in range(Y)]

ans = 0
se = [[0 for _ in range(X)] for _ in range(Y)]
sa = [0 for _ in range(Y)]
for i in range(Y):
    for j in range(X):
        if i * X + j < n:
            ans += re[i][j]
            ans %= MOD
            se[i][j] = re[i][j]
            sa[i] += re[i][j]
            sa[i] %= MOD

de = [[0 for _ in range(X)] for _ in range(Y)]
for i in range(Y):
    for j in range(X):
        if i * X + j < n:
            de[i][j] = 1

for _ in range(q):
    l, r, d = map(int, input().split())
    l, r = n - r, n - l
    for i in range(l // X, r // X + 1):
        if l <= X * i and X * i + X - 1 <= r:
            ans -= sa[i]
            sa[i] = ra[i] * d % MOD
            ans += sa[i]
            ans %= MOD
        else:
            for j in range(X):
                if l <= X * i + j <= r:
                    ans -= se[i][j]
                    sa[i] -= se[i][j]
                    se[i][j] = re[i][j] * d % MOD
                    sa[i] += se[i][j]
                    ans += se[i][j] 
                    ans %= MOD
                    sa[i] %= MOD
                    de[i][j] = d
    print(ans)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
ans="1"*n
while 1:
    l,r,d=map(int,input().split())
    ans=ans[:l]+str(d)*(r-l+1)+ans[r:]
    answer=(int(ans))%998244353
    print(answer)

Submission status: Runtime Error

Solution code:
from decimal import Decimal as dec

n, q = map(int, input().split())
s = "1" * n

for i in range(q):
  l, r, d = map(int, input().split())
  if l != r:
    s = s[:l-1] + str(d) * (r-l+1) + s[r:]
  print(dec(s) % 998244353)

Submission status: Runtime Error

Solution code:
from decimal import Decimal as dec

n, q = map(int, input().split())
s = "1" * n

for i in range(q):
  l, r, d = map(int, input().split())
  s = s[:l-1] + str(d) * (r-l+1) + s[r:]
  print(dec(s) % 998244353)

Submission status: Runtime Error

Solution code:
r=input().split()
N=int(r[0])
Q=int(r[1])
data=int("1"*N)
d=[[int(s) for s in input().split()] for i in range(Q)]
import math
for i in range(Q):
    data=int(math.floor(data/(10**(N-d[i][0]+1))))*(10**(N-d[i][0]+1))+int(str(d[i][2])*(d[i][1]-d[i][0]+1))*(10**(N-d[i][1]))+data%10**(N-d[i][1])
    print(data%998244353)

Submission status: Runtime Error

Solution code:
r=input().split()
N=int(r[0])
Q=int(r[1])
data=int("1"*N)
d=[[int(s) for s in input().split()] for i in range(Q)]
for i in range(Q):
    data=int(math.floor(data/(10**(N-d[i][0]+1))))*(10**(N-d[i][0]+1))+int(str(d[i][2])*(d[i][1]-d[i][0]+1))*(10**(N-d[i][1]))+data%10**(N-d[i][1])
    print(data%998244353)

Submission status: Runtime Error

Solution code:
import numpy as np
mod = 998244353
n, q = map(int, input().split())
s = np.ones(n)
for _ in range(q):
  l, r, d = map(int, input().split())
  s[l-1:r] = d
  print(str(int("".join(s.astype(int).astype(str))) % mod))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split(" "))
A=[1,1,1,1,1,1,1,1]

for i in range(m):
  a,b,x=map(int,input().split(" "))
  c=1
  g=0
  for j in range(a-1,b):
    A[j]=x
  for j in range(n):
    g=A[j]+g*10
  print(g%998244353)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split(" "))
A=[1,1,1,1,1,1,1,1]

for i in range(m):
  a,b,x=map(int,input().split(" "))
  c=1
  g=0
  for i in range(a-1,b):
    A[i]=x
  for j in range(n):
    g=A[j]+g*10
  print(g%998244353)

Submission status: Runtime Error

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
import numpy as np
import sys
import math
import collections
n,q = L()
lrd = NL(q)
b = [1]*n
for l,r,d in lrd:
    for i in range(n):
        if i >= l-1 and i<r:
            print(d,end="")
            b[i]= d
        else:
            print(b[i],end="")
    print()

Submission status: Runtime Error

Solution code:
import atexit
import io
import sys

_INPUT_LINES = sys.stdin.read().splitlines()
raw_input = iter(_INPUT_LINES).next
_OUTPUT_BUFFER = io.BytesIO()
sys.stdout = _OUTPUT_BUFFER


@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

n,m = map(int,raw_input().split())
s = "1"*n
for i in range(m):
  l,r,k = map(int,raw_input().split())
  s =  s[:l-1]+str(k)*(r-l+1)+s[r:]
  write(int(s)%998244353)

Submission status: Runtime Error

Solution code:
#E
n,q = list(map(int, input().split()))
nl=[0]*n
for i in range(q):
    l,r,d=list(map(int, input().split()))
    for j in range(l,r):
        nl[j]=d
    li = map(str, nl)
    print(''.join(li))

num=map(int,li)
ans=num%998244353
print(ans)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
ans="1"*n
while 1:
    l,r,d=map(int,input().split())
    ans=ans[:l]+str(d)*(r-l+1)+ans[r:]
    answer=int(ans)%998244353
    print(answer)

Submission status: Runtime Error

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

N,Q=map(int,input().split())

mod=998244353

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
seg_height=1+N.bit_length() # Segment treeの高さ
SEG=[0 for i in range(2*seg_el)] # 区間の和
LAZY=[0 for i in range(2*seg_el)]


POW10=[pow(10,i,mod) for i in range(N+1)]
gyaku=pow(9,-1,mod)

def seg_function(x,y):
    return (x+y)%mod
    
for i in range(N): # Aを対応する箇所へupdate
    SEG[i+seg_el]=POW10[i]
        
for i in range(seg_el-1,0,-1): # 親の部分もupdate
    SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])

def lazy_change(ind,b):
    kousuu = 1<< (seg_height - (ind.bit_length()))
    tyousei = (ind - (1<<((ind.bit_length())-1)))*kousuu

    #print(ind,tyousei,kousuu)
    SEG[ind] = POW10[tyousei] * b * (POW10[kousuu]-1) * gyaku %mod

def lazy_compose(ind,b):
    LAZY[ind]=b

def indexes(L,R): # 遅延伝搬すべきノードのリストを下から上の順に返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def changes(l,r,b0): # 区間[l,r)更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=0:
            b=LAZY[ind]
            
            lazy_change(ind<<1,b)
            lazy_change(1+(ind<<1),b)
            
            lazy_compose(ind<<1,b)
            lazy_compose(1+(ind<<1),b)
            
            LAZY[ind]=0

    #print(SEG)
    
    while L!=R:
        if L > R:
            lazy_change(L,b0)
            lazy_compose(L,b0)
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            lazy_change(R,b0)
            lazy_compose(R,b0)
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=seg_function(SEG[ind<<1],SEG[1+(ind<<1)])
        
def getvalues(l,r):

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=0:
            b=LAZY[ind]
            
            lazy_change(ind<<1,b)
            lazy_change(1+(ind<<1),b)
            
            lazy_compose(ind<<1,b)
            lazy_compose(1+(ind<<1),b)
            
            LAZY[ind]=0
            
    ANSL=0
    ANSR=0

    while L!=R:
        if L > R:
            ANSL=seg_function(ANSL,SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANSR=seg_function(SEG[R],ANSR)
            R//=(R & (-R))

    return seg_function(ANSL,ANSR)

for qu in range(Q):
    L,R,D=map(int,input().split())
    L,R=N-R+1,N-L+1
    #print(SEG)

    changes(L-1,R,D)
    sys.stdout.write(str(SEG[1])+"\n")

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
MOD = 998244353
a = '1'*n
for _ in range(q):
    ans = 0
    l, r, d = map(int, input().split())

    if l-1 <= n:
        ans += (int(a[:l-1] + '0'*(n-l+1)) % MOD)
    ans += (int(str(d)*(r-l+1) + '0'*(n-r)) % MOD)
    if r < n:
        ans += (int(a[r:]) % MOD)
    ans %= MOD
    print(ans)
    a = str(ans)

Submission status: Runtime Error

Solution code:
r=input().split()
N=int(r[0])
Q=int(r[1])
data="1"*N
d=[input().split() for i in range(Q)]
for i in range(Q):
    data=data[0:int(d[i][0])-1]+d[i][2]*(int(d[i][1])-int(d[i][0]+1))+data[int(d[i][1]):N]
    print(int(data)%998244353)

Submission status: Runtime Error

Solution code:
n, q = map(int,input().split())

s = '1' * n
for _ in range(q):
    l, r, d = map(int,input().split())
    tmp = str(d) * (r - l + 1)
    s = s[:l-1] + tmp + s[r:]
    print(s)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split(" "))

S = "1"*N

for i in range(N):
    L, R, D = input().split(" ")
    L = int(L)
    R = int(R)
    S = S[0:L-1]+D*(R-L+1)+S[R:]
    print(int(S) % 998244353)

Submission status: Runtime Error

Solution code:
# ------------------- fast io --------------------
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")

# ------------------- fast io --------------------
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 = int(input())
    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[i])
    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))