Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    t = i_input()
    for i in range(n-1):
        k = i_input()
        t = t*k/gcd(t,k)
        t = int(t)
    print(t)



if __name__=="__main__":
    main()


Fixed submission:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    t = i_input()
    for i in range(n-1):
        k = i_input()
        t = t*k//gcd(t,k)
    print(t)



if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n = i_input()
    a = i_list()
    b = []
    for i,k in enumerate(a):
        if i%2==0:
            b.append(k)
        else:
            b.insert(0,k)
    if len(a)%2==0:
        print(" ".join(map(str, b)))
    else:
        print(" ".join(map(str, reversed(b))))



if __name__=="__main__":
    main()


Fixed submission:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n = i_input()
    a = i_list()
    even = []
    odd = []
    for i,k in enumerate(a):
        if i%2==0:
            even.append(k)
        else:
            odd.append(k)

    even.reverse()
    even.extend(odd)
    if n%2==0:
        even.reverse()
    print(" ".join(map(str, even)))



if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    s = input()
    len_s = len(s)

    a = []

    def rec(n,m):
        if n == len_s:
            a.append(m)
            return
        elif n > len_s:
            return
        if s[n] == "e":
            rec(n+5, m+"erase")
            rec(n+6, m+"eraser")

        elif s[n] == "d":
            rec(n+5, m+"dream")
            rec(n+7, m+"dreamer")

    ans = rec(0,"")
    if len(a) != 0:
        print("YES")
    else:
        print("NO")







if __name__=="__main__":
    main()


Fixed submission:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    s = list(input())
    s.reverse()
    len_s = len(s)
    t = 0
    while True:
        if t == len_s:
            print("YES")
            exit()
        elif t > len_s:
            break
        else:
            if "".join(s[t:t+5]) == "maerd":
                t += 5
            elif "".join(s[t:t+7]) == "remaerd":
                t += 7
            elif "".join(s[t:t+5]) == "esare":
                t += 5
            elif "".join(s[t:t+6]) == "resare":
                t += 6
            else:
                break
    print("NO")


if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    N = i_input()
    t0,a0 = 1,1

    for i in range(N):
        t1,a1 = i_map()
        f0 = t0//t1
        if t0%t1 != 0:
            f0 += 1
        f1 = a0 // a1
        if a0%a1 != -:
            f1 += 1
        f = max(f0, f1)
        t0, a0 = t1*f, a1*f
    print(t0+a0)


if __name__=="__main__":
    main()


Fixed submission:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    N = i_input()
    t0,a0 = 1,1

    for i in range(N):
        t1,a1 = i_map()
        f0 = t0//t1
        if t0%t1 != 0:
            f0 += 1
        f1 = a0 // a1
        if a0%a1 != 0:
            f1 += 1
        f = max(f0, f1)
        t0, a0 = t1*f, a1*f
    print(t0+a0)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import math
n = int(input())

def num_divisors_trial_division(n):
    num = 0
    for i in range(1, int(math.sqrt(n) + 1e-9) + 1):
        if n % i == 0:
            num += 1
            if n != i ** 2:
                num += 1
    return num

ans = 0
for i in range(1, n):
    ans += num_divisors_trial_division(i)
    #print(i , ans)
print(ans)


Fixed submission:

n = int(input())

# def num_divisors_trial_division(n):
#     num = 0
#     for i in range(1, int(n ** (1 / 2)) + 1):
#         if n % i == 0:
#             num += 1
#             if n != i ** 2:
#                 num += 1
#     return num
#
# ans = 0
# for j in range(1, n):
#     ans += num_divisors_trial_division(j)
#     #print(i , ans)
# print(ans)

ans = 0
for i in range(1, n):
    ans += (n - 1) // i
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
xy = list(list(map(int, input().split())) for _ in range(n))

#print(n, xy)
tmp = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        l = abs(xy[i][0] - xy[j][0]) + abs(xy[i][1] - xy[j][1])
        if tmp <= l:
            tmp = l
print(tmp)


Fixed submission:
n = int(input())
xy = list(list(map(int, input().split())) for _ in range(n))

#print(n, xy)
x_minus_y = []
x_plus_y = []
for i in range(n):
    x_minus_y.append(xy[i][0] - xy[i][1])
    x_plus_y.append(xy[i][0] + xy[i][1])
x_max = max(x_minus_y)
x_min = min(x_minus_y)
y_max = max(x_plus_y)
y_min = min(x_plus_y)

if x_max - x_min >= y_max - y_min:
    print(x_max - x_min)
else:
    print(y_max - y_min)
Buggy python submission (verdict: Runtime Error):
# import numpy as np
# import itertools as it

n = int(input())
a = list(map(int, input().split()))

res = 0
for i in range(n):
    res += a[i] * a[i]

ans = sum(a) * sum(a)
print(((ans - res)//2) % (10 ** 9 + 7))


# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))


Fixed submission:
d, t, s = map(int, input().split())

if d/s <= t:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
s = input()
t = input()

cnt1 = 0
if len(s) == len(t):
    for i in range(len(t)):
        if s[i] != t[i]:
            cnt1 += 1
print(cnt1)
else:
    cnt = []
    for i in range(len(t)):
        for k in range(i + 1, len(t) + 1):
            if t[i:k] in s[i:]:
                cnt.append(k - i)
                print(t[i:k], s[i:], k-i)
            else:
                cnt.append(0)
                #print(t[i:k], k - i)
#print(cnt)
print(len(t) - max(cnt))


Fixed submission:
s = input()
t = input()

cnt = []
for i in range(len(s) - len(t) + 1):
    cnt1 = 0
    for k in range(len(t)):
        if t[k] == s[i: i + len(t)][k]:
            cnt1 += 1
            cnt.append(cnt1)
            #print(t[i:k], s[i:], k-i)
    else:
        cnt.append(0)
            #print(t[i:k], k - i)
#print(cnt)
print(len(t) - max(cnt))

Buggy python submission (verdict: Runtime Error):
s = input()
t = input()

cnt = []
for i in range(len(t)):
    for k in range(i + 1, len(t) + 1):
        if t[i:k] in s[i:]:
            cnt.append(k - i)
            print(t[i:k], k - i)
#print(cnt)
print(len(t) - max(cnt))


Fixed submission:
s = input()
t = input()

cnt = []
for i in range(len(s) - len(t) + 1):
    cnt1 = 0
    for k in range(len(t)):
        if t[k] == s[i: i + len(t)][k]:
            cnt1 += 1
            cnt.append(cnt1)
            #print(t[i:k], s[i:], k-i)
    else:
        cnt.append(0)
            #print(t[i:k], k - i)
#print(cnt)
print(len(t) - max(cnt))

Buggy python submission (verdict: Runtime Error):
s = input()
t = input()

cnt = []
for i in range(len(t)):
    for k in range(i + 1, len(t)):
        if t[i:k] in s[i:]:
            cnt.append(k - i)
            #print(t[i:k])
#print(cnt)
print(len(t) - max(cnt))


Fixed submission:
s = input()
t = input()

cnt = []
for i in range(len(s) - len(t) + 1):
    cnt1 = 0
    for k in range(len(t)):
        if t[k] == s[i: i + len(t)][k]:
            cnt1 += 1
            cnt.append(cnt1)
            #print(t[i:k], s[i:], k-i)
    else:
        cnt.append(0)
            #print(t[i:k], k - i)
#print(cnt)
print(len(t) - max(cnt))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import itertools as it

n = int(input())
a = list(map(int, input().split()))

sum1 = 0
for i in range(n - 1):
    #print(a[i + 1:], a[i])
    #print(sum(a[i + 1:]))
    sum1 += a[i] * sum(a[i + 1:])
if sum1 >= 10 ** 9 + 7:
    sum1 = sum1 % (10 ** 9 + 7)

print(sum1)

# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))


Fixed submission:
# import numpy as np
# import itertools as it

n = int(input())
a = list(map(int, input().split()))

res = 0
for i in range(n):
    res += a[i] * a[i]

ans = sum(a) * sum(a)
print(((ans - res)//2) % (10 ** 9 + 7))


# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import itertools as it

n = int(input())
a = list(map(int, input().split()))

sum1 = 0
for i in range(n - 1):
    #print(a[i + 1:], a[i])
    #print(sum(a[i + 1:]))
    sum1 += a[i] * sum(a[i + 1:])

print(sum1 % (10 ** 9 + 7))

# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))


Fixed submission:
# import numpy as np
# import itertools as it

n = int(input())
a = list(map(int, input().split()))

res = 0
for i in range(n):
    res += a[i] * a[i]

ans = sum(a) * sum(a)
print(((ans - res)//2) % (10 ** 9 + 7))


# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import itertools as it

n = int(input())
a = list(map(int, input().split()))

combinations_lis = list(it.combinations(a, 2))
#print(combinations_lis)

sum = 0
for i in range(len(combinations_lis)):
    sum += combinations_lis[i][0] * combinations_lis[i][1]
print(sum % (10 ** 9 + 7))

# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))


Fixed submission:
# import numpy as np
# import itertools as it

n = int(input())
a = list(map(int, input().split()))

res = 0
for i in range(n):
    res += a[i] * a[i]

ans = sum(a) * sum(a)
print(((ans - res)//2) % (10 ** 9 + 7))


# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

if 0 in a:
    print(0)
else:

    ans = 1
    i = 0
    while (ans < 10 ** 18):
        ans *= a[i]
        i += 1

    if i == n - 1:
        print(ans)
    else:
        print(-1)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

if 0 in a:
    print(0)
else:

    ans = 1
    i = 0
    while (i <= n - 1):
        if ans <= 10 ** 18:
            ans *= a[i]
            i += 1
        else:
            break

    #print(i)
    if ans <= 10 ** 18:
        print(ans)
    else:
        print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

ans = 1
for i in range(n):
    ans *= a[i]

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

if 0 in a:
    print(0)
else:

    ans = 1
    i = 0
    while (i <= n - 1):
        if ans <= 10 ** 18:
            ans *= a[i]
            i += 1
        else:
            break

    #print(i)
    if ans <= 10 ** 18:
        print(ans)
    else:
        print(-1)
Buggy python submission (verdict: Runtime Error):
n, m, x = map(int, input().split())
a = list(list(map(int, input().split())) for _ in range(n))

#print(n, m, x, a)

#0b00・・・０~0b111・・・１を全部作成
cost_abl = []
cost_lis = []
abl_lis = []
for i in range(1 << n):
    cost = 0
    abl_sum = [0] * (len(a))
    #print(abl_sum)
    #abl_1, abl_2, abl_3 = 0, 0 ,0
    for j in range (len(a)):
        mask = 1 << j
        if i & mask:
            cost += a[j][0]
            for k in range(len(a)):
                abl_sum[k] += a[j][k + 1]
            # abl_1 +=  a[j][1]
            # abl_2 += a[j][2]
            # abl_3 += a[j][3]
    cost_lis.append(cost)
    abl_lis.append(abl_sum)
    #print(bin(i))
#print(cost_lis, abl_lis)

cost_new_lis = []
for i in range(len(abl_lis)):
    if min(abl_lis[i]) >= x:
        cost_new_lis.append(cost_lis[i])
    else:
        pass
#print(cost_new_lis)

if cost_new_lis == []:
    print(-1)
else:
    print(min(cost_new_lis))


Fixed submission:
n, m, x = map(int, input().split())
a = list(list(map(int, input().split())) for _ in range(n))

#print(n, m, x, a)

#0b00・・・０~0b111・・・１を全部作成
cost_abl = []
cost_lis = []
abl_lis = []
for i in range(1 << n):
    cost = 0
    abl_sum = [0] * m
    #print(abl_sum)
    #abl_1, abl_2, abl_3 = 0, 0 ,0
    for j in range (len(a)):
        mask = 1 << j
        if i & mask:
            cost += a[j][0]
            for k in range(m):
                abl_sum[k] += a[j][k + 1]
            # abl_1 +=  a[j][1]
            # abl_2 += a[j][2]
            # abl_3 += a[j][3]
    cost_lis.append(cost)
    abl_lis.append(abl_sum)
    #print(bin(i))
#print(cost_lis, abl_lis)

cost_new_lis = []
for i in range(len(abl_lis)):
    if min(abl_lis[i]) >= x:
        cost_new_lis.append(cost_lis[i])
    else:
        pass
#print(cost_new_lis)

if cost_new_lis == []:
    print(-1)
else:
    print(min(cost_new_lis))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))

def ev(n):
    return n * (n + 1) / (2 * n)

ans = 0
for i in range(n - k + 1):
    tmp = 0
    for j in range(i, i + k):
        tmp += ev(p[j])
    if ans <= tmp:
        ans = tmp
    #print(ans, i)
print(ans)


Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))

def ev(n):
    return n * (n + 1) / (2 * n)

q = [0]
for i in range(n):
    q.append(ev(p[i]))
    q[i + 1] = q[i] + ev(p[i])
#print(q)

tmp = 0
for j in range(n - k + 1):
    if tmp <= q[j + k] - q[j]:
        tmp = q[j + k] - q[j]
print(tmp)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()

# print(S.count('ABC'))

cnt = 0
for i in range(N):
    if S[i] == 'A' and S[i + 1] == "B" and S[i + 2] == "C":
        cnt += 1

print(cnt)

Fixed submission:
N = int(input())
S = input()

print(S.count('ABC'))

Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()

# print(S.count('ABC'))

cnt = 0
for i in range(N):
    if S[i] == 'A' and S[i + 1] == "B" and S[i + 2] == "C":
        cnt += 1

print(cnt)


Fixed submission:
N = int(input())
S = input()

print(S.count('ABC'))
Buggy python submission (verdict: Runtime Error):
n = int(input())

ans = []
for i in range(1, n + 1):
    x = i
    for j in range(100):
        if x % 2 == 0:
            x = int(x // 2)
            #ans.append(j)
        else:
            #ans.append(j)
            break
    #ans.append(j)

#print(ans)
print(ans.index(max(ans)) + 1)


Fixed submission:
n = int(input())

ans = []
for i in range(1, n + 1):
    x = i
    for j in range(100):
        if x % 2 == 0:
            x = int(x // 2)
            #ans.append(j)
        else:
            #ans.append(j)
            break
    ans.append(j)

#print(ans)
print(ans.index(max(ans)) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())

cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if s == x + y + z:
                cnt += 1

print(cnt)


Fixed submission:
k, s = map(int, input().split())

cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            cnt += 1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:
    def __init__(self, a):
        self.padding = -float('inf')    
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = max(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = max(self.seg_data[2*idx+1], self.seg_data[2*idx+2])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = max(result, self.seg_data[idx1])
                if idx2&1 == 1: # idx2が奇数
                    result = max(result, self.seg_data[idx2])
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result


N, K = map(int, input().split())
A = 300001
st = SegmentTree([0]*A)

for i in range(N):
    a = int(input())
    l = max(0, a-K)
    r = min(A-1, a+K)
    max_len = st.query(l, r+1)
    st.update(a, max_len+1)

print(st.query(1, A))

Fixed submission:
class SegmentTree:
    def __init__(self, a):
        self.padding = -float('inf')    
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = max(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = max(self.seg_data[2*idx+1], self.seg_data[2*idx+2])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = max(result, self.seg_data[idx1])
                if idx2&1 == 1: # idx2が奇数
                    result = max(result, self.seg_data[idx2])
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result


N, K = map(int, input().split())
A = 300001
st = SegmentTree([0]*A)

for i in range(N):
    a = int(input())
    l = max(0, a-K)
    r = min(A-1, a+K)
    max_len = st.query(l, r+1)
    st.update(a, max_len+1)

print(st.query(1, A))