Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N,Q = [int(i) for i in input().split()]
S = input()
q_list = []
for i in range(Q) :
    q_list.append([int(i) for i in input().split()])

a_indexes = []
# 下処理として、Aの場所だけ覚えておく
for i in range(len(S)) :
    if (S[i] == "A") :
        a_indexes.append(i)

# 幅に応じて、Aの次がCかどうかを判定する
for item in q_list :
    from_index = item[0]
    to_index = item[1]
    # 次の文字がCであることを調べるので、toは1文字手前にする
    target_indexes = [i for i in a_indexes if i >= from_index-1 and i < to_index-1]
    ac_count = 0
    for index in target_indexes :
        if (S[index+1] == "C") :
            ac_count += 1
    
    print(ac_count)


# もちろんTLE。。。
# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     search_str = S[from_index-1:to_index]
#     find_index = 0
#     ac_count = 0
#     while(find_index != -1) :
#         find_index = search_str.find("AC",find_index)
#         if (find_index != -1) :
#             ac_count += 1
#             find_index += 1
#     print(ac_count)

# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     search_str = S[from_index-1:to_index]
    # print(search_str.replace("AC","X").count("X"))
    # print(search_str.count("AC"))
        


### FIXED CODE ###

N,Q = [int(i) for i in input().split()]
S = input()
q_list = []
for i in range(Q) :
    q_list.append([int(i) for i in input().split()])


## No.5
# n番目までに何回ACって出るか調べたらO(N)で済むのでは？
c = 0
ac_list = []
for i in range(len(S)) :
    # Cの位置を基準にする
    if (S[i] == "C" and i > 0 and S[i-1] == "A") :
        c += 1
        ac_list.append(c)
    else :
        ac_list.append(c)

for item in q_list :
    # XXXXA | C だったケースは除外するので、右端は-1する
    ac_count = ac_list[item[1]-1] - ac_list[item[0]-1]
    print(ac_count)



## No.4
# a_indexes = []
# # 下処理として、Aの場所だけ覚えておく
# for i in range(len(S)) :
#     if (S[i] == "A") :
#         a_indexes.append(i)

# # 幅に応じて、Aの次がCかどうかを判定する
# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     # 次の文字がCであることを調べるので、toは1文字手前にする
#     target_indexes = [i for i in a_indexes if i >= from_index-1 and i < to_index-1]
#     ac_count = 0
#     for index in target_indexes :
#         if (S[index+1] == "C") :
#             ac_count += 1
    
#     print(ac_count)


## No.1  もちろんTLE。。。
# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     search_str = S[from_index-1:to_index]
#     find_index = 0
#     ac_count = 0
#     while(find_index != -1) :
#         find_index = search_str.find("AC",find_index)
#         if (find_index != -1) :
#             ac_count += 1
#             find_index += 1
#     print(ac_count)

## No.2,3
# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     search_str = S[from_index-1:to_index]
    # print(search_str.replace("AC","X").count("X"))
    # print(search_str.count("AC"))
### BUGGY CODE ###

# 1 <= N <= 10**5
# N <= M <= 10**9
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())

V = M // N

ans = 1
for i in range(1, V + 1):
    # if i * i > M:
    #     break
    if M % i == 0:
        ans = i
print(ans)


### FIXED CODE ###

# 1 <= N <= 10**5
# N <= M <= 10**9
import sys
input = sys.stdin.buffer.readline
N, M = map(int, input().split())

V = M // N

ans = 1
for i in range(1, V + 1):
    if i * i > M:
        break
    if M % i == 0:
        j = M // i
        if j <= V:
            ans = max(ans, j)
        else:
            ans = max(ans, i)
print(ans)
### BUGGY CODE ###

N = int(input())
N2 = N
count = 0
i = 1

while True:
  if N == i:
    break
  i *= 2
  count += N2
  N2 //= 2

print(count + 1)

### FIXED CODE ###

# 1000000000000
# 1099511627775
N = int(input())
S = 1

while N >= S:
    S *= 2
 
print(S - 1)
### BUGGY CODE ###

a, b = map(int, input().split())

def gcd(a, b):
    if a == b:
        return a
    big = max(a, b)
    small = min(a, b)
    big_i = big % small
    herf = round(min(small, big_i))
    for i in range(herf, 1, -1):
        if small%i==0 and big_i%i==0:
            return i
    return 1
    
print(gcd(a, b))



### FIXED CODE ###

a, b = map(int, input().split())

def gcd(a, b):
    big = max(a, b)
    small = min(a, b)
    while not big % small == 0:
        big, small = small, big%small
    return small
    
print(gcd(a, b))
### BUGGY CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0 and cnt[a]==1:
        ans += 1
    for i in range(10**7):
        x = a*i
        if x>10**6:
            break
        P[x] = 1

print (ans)




### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0:
        for i in range(10**7):
            x = a*i
            if x>10**6:
                break
            P[x] = 1
        if cnt[a]==1:
            ans +=1

print (ans)
### BUGGY CODE ###

n=int(input())

l=[[0 for i in range(n)] for j in range(n)]##静的確保 隣接行列
d=[0 for i in range(n)]##発見
f=[0 for i in range(n)]##完了
stack=[]##スタック
check=[]

for i in range(n):
    p=[int(x) for x in input().split()]
    
    for j in range(n):
        if j+1 in p[2:]:
            l[i][j]=1
##print("---隣接行列---")
##print(l)

time=1


while len(check)<n:
    for i in range(n):
        if i+1 not in check:
            stack+=[i+1]
            d[i]=time
            break
        else: pass

    while len(stack)!=0:
        ##print("----------while---------")
        for i in range(n):
            if l[stack[-1]-1][i]==1 and not i+1 in check and stack[-1]-1!=i:
                time+=1
                d[i]=time
                stack+=[i+1]

               ## print("stack:",stack)
               ## print("check:",check)
               ## print("d[",i,"]:",d[i])
                break
            elif i==n-1:
##最深    
                check+=[stack[-1]]
                time+=1
                f[stack.pop()-1]=time

               ## print("f[",i,"]:",f[i])
               ## print("check:",check)
    time+=1


for i in range(n):
    print(i+1,d[i],f[i])



### FIXED CODE ###


n=int(input())

l=[[0 for i in range(n)] for j in range(n)]##静的確保 隣接行列
d=[0 for i in range(n)]##発見
f=[0 for i in range(n)]##完了
stack=[]##スタック
check=[]

for i in range(n):
    p=[int(x) for x in input().split()]
    
    for j in range(n):
        if j+1 in p[2:]:
            l[i][j]=1
##print("---隣接行列---")
##print(l)

time=1


while len(check)<n:
    for i in range(n):
        if i+1 not in check:
            stack+=[i+1]
            d[i]=time
            break
        else: pass

    while len(stack)!=0:
        ##print("----------while---------")
        for i in range(n):
            if l[stack[-1]-1][i]==1 and not i+1 in check and i+1 not in stack and stack[-1]-1!=i:
                time+=1
                d[i]=time
                stack+=[i+1]

               ## print("stack:",stack)
               ## print("check:",check)
               ## print("d[",i,"]:",d[i])
                break
            elif i==n-1:
##最深    
                check+=[stack[-1]]
                time+=1
                f[stack.pop()-1]=time

               ## print("f[",i,"]:",f[i])
               ## print("check:",check)
    time+=1


for i in range(n):
    print(i+1,d[i],f[i])
### BUGGY CODE ###

n = int(input())
a = list()
for i in range(n):
    a.append(input())
for i, youso in enumerate(a):
    b = list()
    for j in youso:
        b.append(j)
    b.sort()
    x = str()
    for j in b:
        x += j
        a[i] = x
x = 0
for i, youso in enumerate(a):
    for j in range(i, n-1):
        if youso == a[j+1]:
            x += 1
print(x)

### FIXED CODE ###

import math
n = int(input())
a = list()
d = dict()
for i in range(n):
    b = list(input())
    b.sort()
    moji = "".join(b)
    if (moji in d):
        d[moji] += 1
    else:
        d[moji] = 1
x = 0
for i in d:
    if d[i] >=1:
        x += d[i]*(d[i]-1)/2
print(int(x))

#非最適化ソート
# for i in range(n):
#     a.append(input())
# for i, youso in enumerate(a):
#     b = list()
#     for j in youso:
#         b.append(j)
#     b.sort()
#     x = str()
#     for j in b:
#         x += j
#         a[i] = x

#TLE ver.
# for i, youso in enumerate(a):
#     for j in range(i, n-1):
#         if youso == a[j+1]:
#             x += 1
# print(x)

#TLE改良版
# a.sort()
# for i in range(n-1):
#     if a[i] == a[i+1]:
#         for j in range(i+1, n):
#             if a[i] == a[j]:
#                 x += 1
#             else:
#                 break
#     else:
#         continue



#いらない処理
# y = 0
# for i in range(1, x+1):
#     y += i
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e = sorted(e)
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:
            m = stop
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
ans = 0
for i in range(1,10**5):
    dum = li.count(i-1) + li.count(i) + li.count(i+1)
    ans = max(dum,ans)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
li = list(map(int,input().split()))
counter_li = Counter(li)
ans = 0
for i in range(1,10**5):
    dum = counter_li[i-1] + counter_li[i] + counter_li[i+1]
    ans = max(dum,ans)
print(ans)
### BUGGY CODE ###

import itertools
n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(k-1,n):
    ans=(ans+a[i]*(combination(i, k-1, mod=10**9+7)))%(10**9+7)
for i in range(0,n-k+1):
    ans=(ans-a[i]*(combination(n-i-1, k-1, mod=10**9+7)))%(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

mod=10**9+7
f=[1]
for i in range(n):f+=[f[-1]*(i+1)%mod]
def comb(a,b):
    return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

a=list(map(int,input().split()))
a.sort()
b=a[::-1]
#print(a,b)
ans=0
for i in range(k-1,n):
    ans+=((a[i]-b[i])*(comb(i,k-1)))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

H, W = map(int, input().split())
A = []
for i in range(H):
    A.append(list(map(int, input().split())))
B = []
for i in range(H):
    B.append(list(map(int, input().split())))

dp = [[[0] * (H*W*80) for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])] = 1

for i in range(H):
    for j in range(W):
        dif = abs(A[i][j] - B[i][j])
        if i > 0:
            for k in range(H*W*80):
                if dp[i-1][j][k] == 1:
                    dp[i][j][k+dif] = 1
                    if k >= dif:
                        dp[i][j][k-dif] = 1
                    else:
                        dp[i][j][dif-k] = 1
        if j > 0:
            for k in range(H*W*80):
                if dp[i][j-1][k] == 1:
                    dp[i][j][k+dif] = 1
                    if k >= dif:
                        dp[i][j][k-dif] = 1
                    else:
                        dp[i][j][dif-k] = 1

for k in range(H*W*80):
    if dp[H-1][W-1][k] == 1:
        ans = k
        break

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]
center = 80 * (H+W)
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

dp = [[0] * W for i in range(H)]
dp[0][0] = (1 << (center + C[0][0])) | (1 >> (center - C[0][0]))

for i in range(H):
    for j in range(W):
        if i:
            dp[i][j] |= dp[i-1][j] << C[i][j]
            dp[i][j] |= dp[i-1][j] >> C[i][j]
        if j:
            dp[i][j] |= dp[i][j-1] << C[i][j]
            dp[i][j] |= dp[i][j-1] >> C[i][j]

ans = center * 2
for i in range(center*2):
    if (dp[H-1][W-1] >> i) & 1:
        ans = min(ans, abs(i-center))

print(ans)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]!=Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]!=Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
ans=1
for i in range(n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans*=min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)

### FIXED CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]>Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]>Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
if Tres[0]<=Ares[0]:
  ans=1
else:
  ans=0
for i in range(1,n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

v = sorted(set(s))
num = []

for i in v:
    num.append(s.count(i))
d = dict(zip(v, num))
#d_sort = sorted(d.items(), key=lambda x: x[1], reverse=True)

ma = max(d.values())
for i in v:
    if d.get(i)==ma:
        print(i)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]

import collections
c0 = collections.Counter(s)
c1 = c0.most_common()
max = c1[0][1]
l = []
for x, i in c0.items():
    if i == max:
        l.append(x)
ans = sorted(l)
for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, 2*k):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if count[p] == 0 and b%p == 0:
        baisu.append(p)
      c = 0
      while b % p == 0:
        b //= p 
        c += 1 
      if c > count[p]:
        count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, 2*k):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)
### BUGGY CODE ###

n = int(input())
s = [[] for _ in range(n)]
num_of_anaglam = [0 for _ in range(n)]

for i in range(n):
    si = input()
    s[i] = sorted(list(si))
    for j in range(i - 1, -1, -1):
        if s[i] == s[j]:
            num_of_anaglam[i] = 1 + num_of_anaglam[j]
            break

print(sum(num_of_anaglam))

### FIXED CODE ###

n = int(input())
num_of_anagram = dict()
ans = 0

for _ in range(n):
    s = input()
    s = ''.join(sorted(list(s)))
    if s in num_of_anagram:
        num_of_anagram[s] += 1
        ans += num_of_anagram[s]
    else:
        num_of_anagram[s] = 0

print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

# 道の接続マップ
route = [[False for j in range(N)] for i in range(N)]

for a, b in zip(A, B):
    route[a - 1][b - 1] = True
    route[b - 1][a - 1] = True


# 探索する
room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

# 次に行く部屋
stack = [0]
while stack:
    now = stack.pop()
    for j in range(N):
        if route[now][j]:
            # 次の部屋の深さが不明な場合または今の部屋の深さ+1より大きい場合は次の部屋の情報を更新
            if room_depth[j] is None or room_depth[j] > room_depth[now] + 1:
                room_depth[j] = room_depth[now] + 1
                room_sign[j] = now + 1
                stack.append(j)

print('Yes')
for s in room_sign[1:]:
    print(s)



### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

from math import ceil, log2
import sys
z=sys.stdin.readline
class SegTree:
    ide_ele = 0
    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

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

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

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


n, k = map(int, z().split())
a = [int(z()) for _ in range(n)]
M=300001
st = SegTree([0]*M)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, M)
    s = st.query(min_a, max_a+1, 0, 0, st.num)
    st.update(i, max(s, 0)+1)
    res = max(res, max(s, 0) + 1)

print(res)


### FIXED CODE ###

from math import ceil, log2
import sys
z=sys.stdin.readline


# SegTreeの関数
def segfunc(x, y):
    return max(x, y)


# 単位元
# min->inf, max->-inf, add->0, mul->1
ide_ele = -1


# セグメント木
class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセットする
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = 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


n, k = map(int, z().split())
a = [int(z()) for _ in range(n)]
M=300001
st = SegTree([0]*M, max, 0)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, M)
    s = st.query(min_a, max_a+1)
    st.update(i, max(s, 0)+1)
    res = max(res, max(s, 0) + 1)

print(res)