Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x,y):
  n,m = min(x,y), max(x,y)
  while n!=0:
    n, m = m%n, n
  
  return m

def prime(N):
  p = [i+1 for i in range(N)]
  for i in range(2,N+1):
    p = [i_p for i_p in p if i_p%i!=0 or i_p/i==1]

  return p
def prime_factorization(N):
  n = N
  P = prime(int(N**0.5))
  p_f = [1]
  while n != 1:
    for p in P[1:]:
      if n%p == 0:
        p_f.append(p)
        n = n / p
        break
  return p_f

A, B = list(map(int, input().split(" ")))
print(len(set(prime_factorization(gcd(A, B)))))

Fixed submission:
def gcd(x,y):
  n,m = min(x,y), max(x,y)
  while n!=0:
    n, m = m%n, n
  
  return m

def prime_factorization(N):
  f = 2
  p_f = []
  while N%f==0:
    p_f.append(f)
    N //= f
  f = 3
  while f**2 <= N:
    if N%f==0:
      p_f.append(f)
      N //= f
    else: f+=2
  if N!=1: p_f.append(N)
  return p_f

A, B = list(map(int, input().split(" ")))
print(1+len(set(prime_factorization(gcd(A, B)))))

Buggy python submission (verdict: Runtime Error):
def gcd(x,y):
  n,m = min(x,y), max(x,y)
  while n!=0:
    n, m = m%n, n
  
  return m

def prime(N):
  p = [i+1 for i in range(N)]
  for i in range(2,N+1):
    p = [i_p for i_p in p if i_p%i!=0 or i_p/i==1]

  return p
def prime_factorization(N):
  n = N
  P = prime(int(N**0.5))
  p_f = [1]
  while n != 1:
    for p in P[1:]:
      if n%p == 0:
        p_f.append(p)
        n = n / p
        break
  return p_f
A, B = list(map(int, input().split(" ")))
print(len(set(prime_factorization(gcd(A, B))))

Fixed submission:
def gcd(x,y):
  n,m = min(x,y), max(x,y)
  while n!=0:
    n, m = m%n, n
  
  return m

def prime_factorization(N):
  f = 2
  p_f = []
  while N%f==0:
    p_f.append(f)
    N //= f
  f = 3
  while f**2 <= N:
    if N%f==0:
      p_f.append(f)
      N //= f
    else: f+=2
  if N!=1: p_f.append(N)
  return p_f

A, B = list(map(int, input().split(" ")))
print(1+len(set(prime_factorization(gcd(A, B)))))
Buggy python submission (verdict: Time Limit Exceeded):
n, k, q = map(int, input().split())
P = [k]*n
Q = [0]*n
for _ in range(q):
  a = int(input())
  Q = list(map(lambda x,y:x+y, Q,[0 if i+1==a else -1 for i in range(n)]))
P = list(map(lambda x,y: x+y,P,Q))
for p in P: print("Yes" if p>0 else "No")

Fixed submission:
n, k, q = map(int, input().split())
P = [k]*n
Q = [-q]*n
for _ in range(q): Q[int(input())-1]+=1
P = map(lambda x,y:x+y, P,Q)
for p in P: print("Yes" if p>0 else "No")
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

for i in range(M):
  A_max = A[-1]
  if A_max==0: break
  A[-1] //= 2
  A = sorted(A)
print(sum(A))

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))

while M>0:
  A = sorted(A, reverse=True)
  a_ = A[0]//2
  for i,a_i in enumerate(A):
    if a_i > a_ and M>0:
      A[i] = a_i//2
      M -= 1
    else: break
  if a_==0: break
print(sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))

for i in range(M):
  A_max = max(A)
  if A_max==0:break
  A[A.index(A_max)] = A_max//2
print(sum(A))

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))

while M>0:
  A = sorted(A, reverse=True)
  a_ = A[0]//2
  for i,a_i in enumerate(A):
    if a_i > a_ and M>0:
      A[i] = a_i//2
      M -= 1
    else: break
  if a_==0: break
print(sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))

for i in range(M):
  A_max = max(A)
  A[A.index(A_max)] = A_max//2
print(sum(A))

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))

while M>0:
  A = sorted(A, reverse=True)
  a_ = A[0]//2
  for i,a_i in enumerate(A):
    if a_i > a_ and M>0:
      A[i] = a_i//2
      M -= 1
    else: break
  if a_==0: break
print(sum(A))
Buggy python submission (verdict: Runtime Error):
A, B, X = map(int, raw_input().split(" "))
if A==X or (X-A)<=B: print("YES")
else: print("NO")

Fixed submission:
A, B, X = map(int, input().split(" "))
if X==A: print("YES")
elif X<A: print("NO")
else:
  if (X-A)<=B: print("YES")
  else: print("NO")

Buggy python submission (verdict: Runtime Error):
A, B, X = map(int, raw_input().split(" "))
if (X-A)<=B and X>A: print("YES")
else: print("NO")

Fixed submission:
A, B, X = map(int, input().split(" "))
if X==A: print("YES")
elif X<A: print("NO")
else:
  if (X-A)<=B: print("YES")
  else: print("NO")
Buggy python submission (verdict: Runtime Error):
N, M, X = map(int, raw_input().split(" "))
A = map(int, raw_input().split(" "))
r = len([ai for ai in A if ai < X])
l = len([ai for ai in A if ai > X])
print(min((r,l))

Fixed submission:
N, M, X = map(int, input().split(" "))
A = map(int, input().split(" "))
left, right = 0,0
for ai in A:
  if ai < X: left+=1
  else: right+=1
print(min(right, left))

Buggy python submission (verdict: Runtime Error):
N, M, X = map(int, raw_input().split(" "))
A = map(int, raw_input().split(" "))
left, right = 0,0
for ai in A:
  if ai < X: left+=1
  else: right+=1
print(min(right, left))


Fixed submission:
N, M, X = map(int, input().split(" "))
A = map(int, input().split(" "))
left, right = 0,0
for ai in A:
  if ai < X: left+=1
  else: right+=1
print(min(right, left))

Buggy python submission (verdict: Runtime Error):
N, M, X = map(int, input().split(" "))
A = map(int, raw_input().split(" "))
print(min([len([i for i in A if i >= X+1]), len([i for i in A if i <= X-1])]))

Fixed submission:
N, M, X = map(int, input().split(" "))
A = map(int, input().split(" "))
left, right = 0,0
for ai in A:
  if ai < X: left+=1
  else: right+=1
print(min(right, left))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
X = [int(i) for i in input().split()]
for i in range(N): print((lambda j: sorted([x for k, x in enumerate(X) if not k == j]))(i)[N//2-1])

Fixed submission:
N = int(input())
X = [int(i) for i in input().split()]
X_sorted = sorted(X)

X_med = X_sorted[N//2-1:N//2+1]
for xi in X:
  if xi <= X_med[0]: print(X_med[1])
  else: print(X_med[0])

Buggy python submission (verdict: Runtime Error):
N = int(input())
X = [int(i) for i in input().split()]
for i in range(N): print((lambda j: sorted([x for k, x in enumerate(X) if not k == j]))(i)[N/2-1])

Fixed submission:
N = int(input())
X = [int(i) for i in input().split()]
X_sorted = sorted(X)

X_med = X_sorted[N//2-1:N//2+1]
for xi in X:
  if xi <= X_med[0]: print(X_med[1])
  else: print(X_med[0])

Buggy python submission (verdict: Runtime Error):
N = int(input())
X = [int(i) for i in input().split()]
for i in range(N): print((lambda j: sorted([x for k, x in enumerate(X) if not k == j]))(i)[N/2-1])

Fixed submission:
N = int(input())
X = [int(i) for i in input().split()]
X_sorted = sorted(X)

X_med = X_sorted[N//2-1:N//2+1]
for xi in X:
  if xi <= X_med[0]: print(X_med[1])
  else: print(X_med[0])
Buggy python submission (verdict: Time Limit Exceeded):
import copy 
def search(A):
  B = list(set(A))
  B.sort(reverse=True)
  if len(A)-len(B) < 2: return (0,0)
  else:
    a1,a2 = 0,0
    for a in copy.deepcopy(B):
      A.pop(A.index(a))
      if a in A:
        A.pop(A.index(a))
        a1 = a
        break
      else:
        B.pop(B.index(a))

    if a1 > 0:
      B = list(set(A))
      B.sort(reverse=True)
      if len(A)-len(B) == 0: return (a1,0)
      for a in copy.deepcopy(B):
        if a in A: A.pop(A.index(a))
        if a in A:
          A.pop(A.index(a))
          a2 = a
          break
        else:
          B.pop(B.index(a))
  return (a1,a2)

N = int(input())
A = map(int, input().split())
A = [a for a in A]
A.sort(reverse=True)
a1, a2 = search(A)
if a1 > 0 and a2 > 0: print(a1*a2)
else: print(0)


Fixed submission:
import numpy as np

def search(A):
  B = list(set(A))
  B.sort(reverse=True)
  if len(A)-len(B) == 0: return 0 

  a1 = 0
  An = np.array(A)
  for n,(i, j) in enumerate(zip(An[0:-1], An[1:])):
    if i == j:
      a1 = i
      break
  del(A[:n+2])

  return a1

N = int(input())
A = map(int, input().split())
A = [a for a in A]
A.sort(reverse=True)
a1 = search(A)
a2 = search(A)
if a1 > 0 and a2 > 0: print(a1*a2)
else: print(0)
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
x = [False]*N
n,i = (0, 0)
while x[n] == False:
    x[n] = True
    n = a[n]-1
    i+=1
    if n==1:
        print(i)
        break
else:
    print(-1)

Fixed submission:
X, A, B = map(int, input().split())
if B <= A: print('delicious')
elif B <= A + X: print('safe')
else: print('dangerous')
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
x = [False]*N
n,i = (1, 0)
while x[n-1] == False:
    x[n] = True
    n = a[n-1]
    i+=1
    if n==2:
        print(i)
        break
else:
    print(-1)

Fixed submission:
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
x = [False]*N
n,i = (0, 0)
while x[n] == False:
    x[n] = True
    n = a[n]-1
    i+=1
    if n==1:
        print(i)
        break
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
if not(2 in a):
    print(-1)

x = [False]*N
n,i = (1, 0)
while x[n] == False:
    x[n] = True
    n = a[n-1]
    i+=1
    if n==2:
        print(i)
        break
else:
    print(-1)

Fixed submission:
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
x = [False]*N
n,i = (0, 0)
while x[n] == False:
    x[n] = True
    n = a[n]-1
    i+=1
    if n==1:
        print(i)
        break
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
import math
N, M = map(int, input().split())

if N-M == 0:
    n = 2*math.factorial(N)*math.factorial(M)
    n %= int(7+1e9)
    print(n)
elif abs(N-Mi) == 1:
    n = math.factorial(N)*math.factorial(M)
    n %= int(7+1e9)
    print(n)
else:
    print(0)

Fixed submission:
import math
N, M = map(int, input().split())
if N-M == 0:
    n = 2*math.factorial(N)*math.factorial(M)
    n %= int(7+1e9)
    print(n)
elif abs(N-M) == 1:
    n = math.factorial(N)*math.factorial(M)
    n %= int(7+1e9)
    print(n)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
N,X,M = map(int,input().split())
dps = [X%M]
rt = 0
while True:
  d = (dps[-1]**2)%M
  if d not in dps:
    dps.append(d)
    if N == len(dps):
      print(sum(dps))
      break
  else:
    ki = dps.index(d)
    RP = (N-ki) // len(dps[ki:])
    mod = (N-ki) % len(dps[ki:])
    print(sum(dps[:ki]) + RP*sum(dps[ki:])+sum(dps[ki:ki+mod]))
    break


Fixed submission:
n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Buggy python submission (verdict: Time Limit Exceeded):
N,X,M = map(int,input().split())
dps = [X%M]
rt = 0
while True:
  d = (dps[-1]**2)%M
  if d not in dps:
    dps.append(d)
  else:
    ki = dps.index(d)
    break
RP = (N-ki) // len(dps[ki:])
mod = (N-ki) % len(dps[ki:])
rt = sum(dps[:ki]) + RP*sum(dps[ki:])+sum(dps[ki:ki+mod])
print(rt)

Fixed submission:
n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Buggy python submission (verdict: Runtime Error):
N,X,M = map(int,input().split())
rt = 0
for i in range(2,N+1):
  dps[i] = (dps[i-1]**2)%M
  rt+=dps[i]
print(rt)

Fixed submission:
n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Buggy python submission (verdict: Time Limit Exceeded):
N,X,M = map(int,input().split())
dps = [0,X%M]+[0 for i in range(N)]

for i in range(2,N+1):
  dps[i] = (dps[i-1]**2)%M
  
print(sum(dps))

Fixed submission:
n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
Buggy python submission (verdict: Runtime Error):
S = int(input())
dp=[1]+[0 for i in range(S)]
i = 3
k=1000000007
while True:
  dp[i]=(dp[i-1]+dp[i-3])%k
  if i == S:
    print(dp[-1])
    break
  i+=1

Fixed submission:
S = int(input())
dp=[1]+[0 for i in range(S)]
i = 3
k=1000000007
if S <3:
  print(0)
else:
  while i <= S:
    dp[i]=(dp[i-1]+dp[i-3])%k
    i+=1
  print(dp[S])
Buggy python submission (verdict: Runtime Error):

D,T,S = map(int, input.split())

print("Yes" if D/(S*T)<=1 else "No")

Fixed submission:

D,T,S = map(int, input().split())

print("Yes" if D/(S*T)<=1 else "No")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int,input().split()))
sums = 0
moder = 1000000007
for i in range(N-1):
  for j in range(N-i-1):
    sums+=(As[i]*As[i+j+1])%moder
print(sums%moder)

Fixed submission:
N = int(input())
As = list(map(int,input().split()))
sums = 0
moder = 1000000007
s=[0 for i in range(N-1)]
s[-1] = As[-1]
for i in range(N-2):
  s[-(i+2)] = s[-(i+1)]+As[-(i+2)]

for i in range(N-1):
  sums+= (As[i]*s[i])%moder
print(sums%moder)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int,input().split()))
sums = 0
moder = 1000000007
for i in range(N-1):
  for j in range(N-i-1):
    sums+=(As[i]*As[i+j+1])
print(sums%moder)

Fixed submission:
N = int(input())
As = list(map(int,input().split()))
sums = 0
moder = 1000000007
s=[0 for i in range(N-1)]
s[-1] = As[-1]
for i in range(N-2):
  s[-(i+2)] = s[-(i+1)]+As[-(i+2)]

for i in range(N-1):
  sums+= (As[i]*s[i])%moder
print(sums%moder)
Buggy python submission (verdict: Runtime Error):
import math
 
X,K,D = map(int, input().split())
tm = round(X/D)
if K <= tm:
  print(abs(X+D*K)if absabs(X+D*K) < abs(X-D*K)else abs(X-D*K))
else:
  if (K-tm)%2==1:
    print(abs(X-D*(tm+1)) if abs(X-D*(tm+1)) < abs(X-D*(tm-1))else abs(X-D*(tm-1)))
  else:
    print(abs(X+D*K)if absabs(X+D*K) < abs(X-D*K)else abs(X-D*K))

Fixed submission:
X, K, D = map(int, input().split())
 
Xa = abs(X)
Xs = Xa // D
Xm = Xa % D
 
if (K <= Xs):
    print(abs(Xa-D*K))
elif (K-Xs) % 2 == 0:
    print(abs(Xm))
else:
    print(abs(D-Xm))

Buggy python submission (verdict: Time Limit Exceeded):
import math

X,K,D = map(int, input().split())
for i in range(K):
  if abs(X-D) < abs(X+D):
    X-=D
  else:
    X+=D
print(abs(X))

Fixed submission:
X, K, D = map(int, input().split())
 
Xa = abs(X)
Xs = Xa // D
Xm = Xa % D
 
if (K <= Xs):
    print(abs(Xa-D*K))
elif (K-Xs) % 2 == 0:
    print(abs(Xm))
else:
    print(abs(D-Xm))

Buggy python submission (verdict: Runtime Error):
import math

X,K,D = map(int, input().split())
tm = round(X/D)
if K <= tm:
  print(abs(X-D*K))
else:
  if (K-tm)%2==1:
    if math.modf(X/D)<0.5:
      print(abs(X-D*(tm+1)))
    else:
      print(abs(X-D*(tm-1)))
  else:
    print(abs(X-D*tm))

Fixed submission:
X, K, D = map(int, input().split())
 
Xa = abs(X)
Xs = Xa // D
Xm = Xa % D
 
if (K <= Xs):
    print(abs(Xa-D*K))
elif (K-Xs) % 2 == 0:
    print(abs(Xm))
else:
    print(abs(D-Xm))
Buggy python submission (verdict: Runtime Error):
N,D=map(int,input().split())
d2 = D**2
rt = 0
for i in range(n):
  x,y = map(int,input().split())
  
  if x**2 + y**2 < d2:
    rt+=1
print(rt)

Fixed submission:
N,D=map(int,input().split())
d2 = D**2
rt = 0
for i in range(N):
  x,y = map(int,input().split())
  
  if x**2 + y**2 <= d2:
    rt+=1
print(rt)
Buggy python submission (verdict: Runtime Error):
d=input()
a=list(map(int,input().split()))
rt=0
for i in a:
  if i % 2 == 1:
    pass
  else:
    if i%3==0 or i%5==0:
      rt=1
    else:
      rt=0
      print("DENIED")
      break
if rt==1:
  print("APPROVED")

Fixed submission:
a=list(map(int,input().split()))
if(a[0]==a[1]==a[2]):
  print("No")
else:
  if (a[0]==a[1])|(a[1]==a[2])|(a[2]==a[0]):
    print("Yes")
  else:
    print("No")

Buggy python submission (verdict: Runtime Error):
d=input()
a=list(map(int,input().split()))
rt=0
print(a)
for i in a:
  if i % 2 == 1:
    pass
  else:
    if i%3==0 or i%5==0:
      rt=1
    else:
      rt=0
      print("DENIED")
      break
if rt==1:
  print("APPROVED")

Fixed submission:
a=list(map(int,input().split()))
if(a[0]==a[1]==a[2]):
  print("No")
else:
  if (a[0]==a[1])|(a[1]==a[2])|(a[2]==a[0]):
    print("Yes")
  else:
    print("No")
Buggy python submission (verdict: Runtime Error):
from collections import Counter
a = Counter(input()).most_common()

print("Yes" if a[1][1]==2 else "No")

Fixed submission:
from collections import Counter
a = Counter(input()).most_common()
if len(a)==2:
  if a[1][1]==2:
    print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
a,sums= list(map(int,input().split()))
print(a)
yuki = sums//10000
taishi = (sums%10000) //5000
noguchi = (sums%5000) //1000
while a<yuki+taishi+noguchi:
  if a-(yuki+taishi+noguchi)%4==0:
    taishi-=1
    noguchi+=5
  else:
    yuki-=1
    taishi+=2
if a==yuki+taishi+noguchi:
  print(yuki,taishi,noguchi)
else print("-1 -1 -1")

Fixed submission:
a,sums= list(map(int,input().split()))
yuki = sums//10000
taishi = (sums%10000) //5000
noguchi = (sums%5000) //1000
while a>yuki+taishi+noguchi:
  if ((a-(yuki+taishi+noguchi))%4==0)&(taishi>0):
    taishi-=1
    noguchi+=5
  elif yuki>0:
    yuki-=1
    taishi+=2
  else:
    break
if a==yuki+taishi+noguchi:
  print(yuki,taishi,noguchi)
else:
  print("-1 -1 -1")
Buggy python submission (verdict: Runtime Error):
A,B = map(int,input().split())
return A+B % 24

Fixed submission:
A,B = map(int,input().split())
print((A+B) % 24)
Buggy python submission (verdict: Runtime Error):
a = input().split()
tg = a[0]
ok_nums = set("1","2","3","4","5","6","7","8","9","0")
ng_nums = set(input().split())
ok_nums = ok_nums - ng_nums
rt = 0
i = int(tg)
while True:
  if ok_nums >= set(d for d in str(i)):
    print(i)
    break
  else:
    i+=1
 

Fixed submission:
a = input().split()
tg = a[0]
ok_nums = set(str(i) for i in range(10))
ng_nums = set(i for i in input().split())
ok_nums = ok_nums - ng_nums
rt = 0
i = int(tg)
intg = int(tg)
while intg > rt:
  if ok_nums >= set(d for d in str(i)):
    rt = i
  else:
    i+=1

print(rt)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    idEle = -INF  # max
    def _binOpe(x, y):
        return x if x >= y else y  # max
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iA, A):
        iST = iA + numPow2
        data[iST] = A  # set
    def update(iA, A):
        _update1(iA, A)
        iST = iA + numPow2
        while iST > 1:
            iST >>= 1
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans


    N, K = map(int, input().split())
    As = [int(input()) for _ in range(N)]

    maxA = max(As)

    data, numPow2 = makeSegTree(maxA+1)
    setInit([0]*(maxA+1))

    for A in As:
        L, R = A-K, A+K
        if L < 0:
            L = 0
        if R > maxA:
            R = maxA
        v = getValue(L, R+1)
        update(A, v+1)

    ans = getValue(0, maxA+1)
    print(ans)


solve()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    INF = float('inf')

    idEle = -INF  # max
    def _binOpe(x, y):
        return x if x >= y else y  # max
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iA, A):
        iST = iA + numPow2
        data[iST] = A  # set
    def update(iA, A):
        _update1(iA, A)
        iST = iA + numPow2
        while iST > 1:
            iST >>= 1
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans


    N, K = map(int, input().split())
    As = [int(input()) for _ in range(N)]

    maxA = max(As)

    data, numPow2 = makeSegTree(maxA+1)
    setInit([0]*(maxA+1))

    for A in As:
        L, R = A-K, A+K
        if L < 0:
            L = 0
        if R > maxA:
            R = maxA
        v = getValue(L, R+1)
        update(A, v+1)

    ans = getValue(0, maxA+1)
    print(ans)


solve()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
As = list(map(int, input().split()))

def isOK(L):
    num = 0
    for A in As:
        num += -(-A // L) - 1
    return num <= K

ng, ok = 0, 10**9
while abs(ok-ng) > 10**-6:
    mid = (ng+ok) / 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

k = int(-(-ok // 1))
#print('ok:', ok, '/ k:', k)

for L in range(max(1, k-2), k+3):
    if isOK(L):
        print(L)
        break


Fixed submission:
N, K = map(int, input().split())
As = list(map(int, input().split()))

def isOK(L):
    num = 0
    for A in As:
        num += -(-A // L) - 1
    return num <= K

ng, ok = 0, 10**9
while abs(ok-ng) > 10**-6:
    mid = (ng+ok) / 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

k = int(-(-ok // 1))
#print('ok:', ok, '/ k:', k)

for L in range(max(1, k-2), k+3):
    if isOK(L):
        print(L)
        break