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

#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    a = [[0]*(N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        a[l][r] += 1

    for i in range(1, N+1):
        a[i] = list(itertools.accumulate(a[i]))

    for pp, qq in zip(p, q):
        print(int(sum([a[i][qq]-a[i][pp-1] for i in range(pp, qq+1)])))
    # print(a)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


class Bit:
    def __init__(self, n, m):
        self.size = [n, m]
        self.tree = [[0] * (n + 1) for _ in range(m+1)]

    def sum(self, i, j):
        s = 0
        while i > 0:
            jj = j
            while jj > 0:
                s += self.tree[i][jj]
                jj -= jj & -jj
            i -= i & -i
        return s

    def add(self, i, j, x):
        while i <= self.size[0]:
            jj = j
            while jj <= self.size[1]:
                self.tree[i][jj] += x
                jj += jj & -jj
            i += i & -i


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    b = Bit(N, N)

    for l, r in zip(L, R):
        b.add(N-l+1, r, 1)

    for pp, qq in zip(p, q):
        print(b.sum(N-pp+1, qq))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,m=map(int,input().split())

ans=0
for i in range(1,m//n+1):
    if m%i==0 :
        ans=i
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())

ans=0
for i in range(1,int(m**0.5)+2):
    if m%i==0 :
        a=m//i
        if min(a,i)>=n :
            ans=max(ans,max(a,i))
        elif max(a,i)>=n :
            ans=max(ans,min(a,i))
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
count = 0
L.sort()
#print(L)
for i in range(N-2):
    a = L[i]
    for j in range(i+1,N-1):
        limit = N
        b = L[j]
        c = L[j+1]

        #もしどうやっても無理な値を見つけたとき
        for k in range(j+1,N):
            if L[k]>a+b:
                limit = k
                break

        if a<b+c and b<a+c and c<a+b:
            count += (limit-1) - j
            #print(a,b,c,i,j,j+1,"limit=",limit,"count=",count)

print(count)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(1,N-1):
  for j in range(i+1,N):
    m = bisect.bisect_right(L,L[j]-L[i])
    if i>m:
      ans += i-m
print(ans)
### BUGGY CODE ###

N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)

p = [0]*(C+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b
        if p[n] > 0:
            p[i] += p[n]
            break

for i in range(1, N+1):
    d = D
    c = C
    if X[i-1] == "1":
        c -= 1
        d -= 1 << (N-i)
    else:
        c += 1
        d += 1 << (N-i)

    if c == 0:
        print(0)
    else:
        d = d % c
        print(p[d]+1)


### FIXED CODE ###

N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)
Mm, Mp = 0, D % (C+1)
if C > 1:
    Mm = D % (C-1)

p = [0]*(2*10**5+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b

for i in range(1, N+1):
    c = C
    if X[i-1] == "1":
        c -= 1
        if c == 0:
            print(0)
            continue
        m = Mm
        d = pow(2, N-i, c)
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = pow(2, N-i, c)
        d = (m+d) % c

    print(p[d]+1)
### BUGGY CODE ###

from fractions import gcd
import itertools
k = int(input())

result = 0

# 3つとも等しい数字
for i in range(1, k+1):
    result += i

# 2つが等しくて、1つが異なる数字
for i in range(1, k+1):
    liste = list(range(1, k+1))
    liste.pop(i-1)
    for j in liste:
        result += (gcd(i, j))*3

# 3つとも異なる
for set in list(itertools.combinations(range(1, k+1), 3)):
    result += (gcd(gcd(set[0], set[1]), set[2]))*6

print(result)



### FIXED CODE ###

from math import gcd
k = int(input())
result = 0

# 3つとも等しい数字
for i in range(1, k+1):
    for j in range(i, k+1):
        for m in range(j, k+1):
            if i==j==m:
                result += i
            elif i==j or j==m:
                result += gcd(i, m)*3
            else:
                result += gcd(i, gcd(j,m))*6
print(result)
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
	a=input()
	if a=="1":
		s=s[::-1]
	else:
		a,f,c = a.split()
		f=int(f)
		if f==1:
			s=c+s
		else:
			s=s+c
print(s)

### FIXED CODE ###

from collections import deque

deq=deque()
k = input()
for i in range(len(k)):
	deq.append(k[i])
q=int(input())
x=True
for i in range(q):
	a=input()
	if a[0]=="1":
		x = not x
	elif a[2]=="1":
		if x==True:
			deq.appendleft(a[4])
		else:
			deq.append(a[4])
	else:
		if x==True:
			deq.append(a[4])
		else:
			deq.appendleft(a[4])
if x==True:
	c="".join(deq)
else:
	deq.reverse()
	c="".join(deq)
print(c)
### BUGGY CODE ###

N,M = map(int, input().split())
P = []
Y = []
O = [[] for i in range(N)]

for i in range(M):
    p,y = map(int, input().split())
    P.append(p)
    Y.append(y)
    O[p-1].append(y)

for o in O:
    o.sort()

for i,p in enumerate(P):
    s = (6 - len(str(p))) * "0"
    s += str(p)
    s += (6 - len(str((O[p-1].index(Y[i])) + 1))) * "0"
    s += str((O[p-1].index(Y[i])) + 1)
    print( s )

### FIXED CODE ###

N,M = map(int, input().split())
O = []

for i in range(M):
    p,y = map(int, input().split())
    O.append([i+1, p, y])
O.sort(key=lambda x:x[2])
count=[0 for i in range(N)]

ans = []
for o in O:
    count[o[1]-1]+=1
    ans.append([o[0], o[1], count[o[1]-1]])
ans.sort(key=lambda x:x[0])

for v in ans:
    a1 = str(v[1])
    s = (6 - len(a1)) * "0"
    s += a1
    a2 = str(v[2])
    s += (6 - len(a2)) * "0"
    s += a2
    print( s )
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))


ans = 0
for i in range(N):
    a, b, c, d = -1, -1, N, N
    for L in range(i - 1, -1, -1):
        if P[L] > P[i]:
            if b == -1:
                b = L
            elif a == -1:
                a = L
            else:
                break
    for R in range(i + 1, N):
        if P[R] > P[i]:
            if c == N:
                c = R
            elif d == N:
                d = R
            else:
                break
    left = (b - a) * (c - i)
    right = (d - c) * (i - b)
    ans += P[i] * (left + right)

print(ans)


### FIXED CODE ###

class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        # for i in range(len(A)):
        #     self.__node[i + n] = A[i]
        # for i in range(n - 1, 0, -1):
        #     self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree([-1] * N, max, -1)
    minSeg = SegmentTree([N] * N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    l = LI()
    l.sort()
    ans = 0
    s = []
    for i in range(n):
        ans += len(s)-bisect.bisect_right(s,l[i])
        for j in range(i):
            s.append(l[i]+l[j])
        s.sort()
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    l = LI()
    l.sort()
    ans = 0
    for i in range(n):
        a = l[i]
        for j in range(i):
            b = l[j]
            c = a+b
            k = bisect.bisect_left(l,c)-i-1
            ans += k
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

for i in range(N):
  push(q, [- A[i] * F[i], A[i], F[i]])

for i in range(K):
  x, y, z = pop(q)
  if y == 0:
    print(0)
    exit()
  push(q, [- (y - 1) * z, y - 1, z])

t = pop(q)
print(-t[0])

### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse = True)

M = 0
for i in range(N):
  M += A[i] * F[i]

def nasu(n):
  ans = 0
  for i in range(N):
    ans += max(0, A[i] - (n // F[i]))
  if ans <= K:
    return True
  else:
    return False

def hersCode():
  ok = M
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

print(hersCode())
### BUGGY CODE ###

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

A    = [int(input()) for _ in range(M)]

dp = [0]*(N+3)



for i in range(N+1):

    if i==0:
        if not (i+1) in A:
            dp[i+1] = 1 + dp[i]
        if not (i+2) in A:
            dp[i+2] = 1 + dp[i]
        continue 
    if not i+1 in A:
        dp[i+1] = dp[i] + dp[i+1]
    if not i+2 in A:
        dp[i+2] = dp[i] + dp[i+2]

print(dp[N]%(1000000007))

### FIXED CODE ###

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

A    = set([int(input()) for _ in range(M)])

dp = [0]*(N+3)



for i in range(N+1):

    if i==0:
        if not (i+1) in A:
            dp[i+1] = 1 + dp[i]
        if not (i+2) in A:
            dp[i+2] = 1 + dp[i]
        continue 
    if not i+1 in A:
        dp[i+1] = dp[i] + dp[i+1]
    if not i+2 in A:
        dp[i+2] = dp[i] + dp[i+2]

print(dp[N]%(1000000007))
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = tuple(map(int, input().split()))


d = {}
for i in range(1, N+1):
    for j in range(1, N+1):
        d[(i, j)] = -1
    d[(i, i)] = 0

for _ in range(M):
    a, b, c = map(int, input().split())

    d[(a, b)] = c
    d[(b, a)] = c

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            d[(i, j)] = min(d[(i, j)], d[(i, k)] + d[(k, j)])


ans = -1
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[(p[i], p[i+1])]

    if ans < 0:
        ans = dist
    else:
        ans = min(ans, dist)

print(ans)


### FIXED CODE ###

import itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = tuple(map(int, input().split()))

INF = 10**10

d = [[INF] * N for _ in range(N)]

for i in range(N):
    d[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    if d[a][b] > c:
        d[a][b] = c
        d[b][a] = c

# for k in range(N):
#     for i in range(N):
#         for j in range(N):
#             d[i][j] = min(d[i][j], d[i][k] + d[k][j])

d = floyd_warshall(d)


ans = INF
for p in itertools.permutations(r):
    dist = 0
    for i in range(R-1):
        dist += d[p[i]-1][p[i+1]-1]

    ans = min(ans, dist)

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

def check(P):
    lis = [[] for i in range(k)]
    su = [0 for i in range(k)]
    
    su.append(-10000)
    for i, bag in enumerate(baggage):
        cur = 0
        #print(su,cur,su[cur])
        while su[cur] + bag > P:
            cur += 1
        if cur == k:
            return False
        else:
            lis[cur].append(bag)
            su[cur] += bag
    #print(lis, su, P)
    return True

def main():
    min_P = 1000000000
    left = 1
    right = 1000000000
    while left < right:
        mid = (left + right)//2 + 1
        #print(left, mid, right, end=" ")
        if check(mid):
            right = mid
            if min_P > mid:
                min_P = mid
        else:
            left = mid+1
    
    #print(left,right)
    print(min_P)
       
if __name__ == '__main__':
    n, k = map(int, input().rstrip().split(" "))
    #n,k= 5,3
    baggage = [int(input()) for i in range(n)]
    #baggage = [8,1,7,3,9]
    
    main()


### FIXED CODE ###

def check(P):
    lis = [[] for i in range(k)]
    su = [0 for i in range(k)]
    
    su.append(-10000)
    cur = 0
    for i, bag in enumerate(baggage):
        #cur = 0
        #print(su,cur,su[cur])
        while su[cur] + bag > P:
            cur += 1
        if cur == k:
            return False
        else:
            lis[cur].append(bag)
            su[cur] += bag
    #print(lis, su, P)
    return True

def main():
    min_P = 1000000000
    left = 1
    right = 1000000000
    mid = (left + right)//2
    while  left < right:
        '''if (left + right) % 2 == 0:
            mid = (left + right)//2
        else:
            mid = (left + right)//2 + 1
        #print(left, mid, right, end=" ")'''
        
        if check(mid):
            right = mid
            if min_P > mid:
                min_P = mid
        else:
            left = mid + 1
        mid = (left + right)//2
    #print(left,right)
    print(min_P)
if __name__ == '__main__':
    n, k = map(int, input().rstrip().split(" "))
    #n,k= 5,3
    baggage = [int(input()) for i in range(n)]
    #baggage = [8,1,7,3,9]
    
    main()
### BUGGY CODE ###

A, B = map(int, input().split())

def make_divisors(a, b):
    n = min(a, b)
    m = max(a, b)
    import math
    divisors = []
    for i in range(2, n + 1):
        if n == 0:
            break
        if n % i == 0: #割り切れるとき
            if m % i == 0:
                divisors.append(i)
            while n % i == 0 and n != 1:
                n //= i
            if n == 1:
                break
    divisors.sort()
    return divisors

lst = make_divisors(A, B) #この中から素数を数えたらいい
print (len(lst) + 1)


### FIXED CODE ###

A, B = map(int, input().split())

def make_divisors(a, b):
    n = min(a, b)
    m = max(a, b)
    import math
    divisors = []
    for i in range(2, int(math.sqrt(n)) + 1):
        if n == 1:
            break
        if n % i == 0: #割り切れるとき
            if m % i == 0:
                divisors.append(i)
            while n % i == 0 and n != 1:
                n //= i
    if n != 1 and m % n == 0:
        divisors.append(n)
    return divisors

lst = make_divisors(A, B) #この中から素数を数えたらいい
print (len(lst) + 1)
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
ans1 = 0
for i in range(N -K +1):
  ans2 = sum(A[i:i+K])
  if ans2 > ans1:
    ans1 = ans2
    ans_list = list(A[i:i+K])
#print(ans_list)
answer = 0
for i in ans_list:
  result = sum(range(1,i+1))/i
  #print(result)
  answer += result

print(answer)
  

### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,k=MI()
	p=LI()

	for i in range(n):
		p[i]=p[i]/2+0.5
	#print(p)

	ans=sum(p[:k])
	now=sum(p[:k])

	for i in range(n-k):
		now=now-p[i]+p[i+k]
		ans=max(ans,now)
	print(ans)















if __name__ == "__main__":
	main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 

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

T = [[]for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)

X = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    X[p-1] += x

def dfs(x, p):
    for j in T[x]:
        if j == p:
            continue
        X[j] += X[x]
        dfs(j, x)

dfs(0, -1)

for i in range(N):
    print(X[i], end =" ")


### FIXED CODE ###

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

F = [0 for i in range(N)]
T = [[]for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    T[a-1].append(b-1)

X = [0 for i in range(N)]
for i in range(Q):
    p, x = map(int, input().split())
    X[p-1] += x

ans = [X[i] for i in range(N)]
for i in range(N):
    F[i] = 1
    for j in range(len(T[i])):
        if F[T[i][j]] == 1:
            continue
        ans[T[i][j]] += ans[i]

for i in range(N):
    print(ans[i], end =" ")
### BUGGY CODE ###

class SegmentTree():

    def __init__(self,N):
        # N: 処理する区間の長さ
        self.N0 = 2**(N-1).bit_length()
        self.INF = 2**31-1
        self.data = [self.INF]*(2*self.N0)
    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])
    # 区間[l, r)の最小値
    def query(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

def main():
    n,k = tuple([int(t)for t in input().split()])
    size = 3*10**5
    lst = SegmentTree(size+1)
    for _ in range(n):
        a = int(input())
        l,r = max(a-k,0),min(a+k+1,size+1)
        m = min(lst.query(l,r),0)
        lst.update(a,m-1)

    print(-lst.query(0,3*10**5))

if __name__ == "__main__":
    main()

### FIXED CODE ###

class SegmentTree():

    def __init__(self,N):
        # N: 処理する区間の長さ
        self.N0 = 2**(N-1).bit_length()
        self.INF = 2**31-1
        self.data = [self.INF]*(2*self.N0)
    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])
    # 区間[l, r)の最小値
    def query(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

def main():
    n,k = tuple([int(t)for t in input().split()])
    size = 3*10**5
    lst = SegmentTree(size+1)
    for _ in range(n):
        a = int(input())
        l,r = max(a-k,0),min(a+k+1,size+1)
        m = min(lst.query(l,r),0)
        lst.update(a,m-1)

    print(-lst.query(0,3*10**5))

if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

for i in range(k):
    if a >= 1:
        a -= 1
    elif b >= 1:
        b -= 1

print('{} {}'.format(a, b))


### FIXED CODE ###

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

if a >= k:
    a = a - k
    print('{} {}'.format(a, b))
elif k <= a + b:
    b = b - (k - a)
    a = 0
    print('{} {}'.format(a, b))
else:
    a = 0
    b = 0
    print('{} {}'.format(a, b))
### BUGGY CODE ###

n = int(input())
l = []
l[:] = map(int,input().split())
l.sort()

c = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        k=n-1
        while (k>=j+1):
            if(ab<=l[k]):
                k-=1
            else:
                break
        c+=(k-j)
print(c)


### FIXED CODE ###

from bisect import bisect_right

n = int(input())
l = list(map(int,input().split()))
l.sort() # 昇順にソート

count = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        # bisect_left(a, x): x を a に挿入できる点を返す
        # cの最大値は a+b-1
        k = bisect_right(l, ab-1, j+1, n)
        count += k-(j+1)
print(count)