Everyone loves a freebie. Especially students.

It is well-known that if in the night before exam a student opens window, opens the student's record-book and shouts loudly three times "Fly, freebie, fly!" — then flown freebie helps him to pass the upcoming exam.

In the night before the exam on mathematical analysis n students living in dormitory shouted treasured words. The i-th student made a sacrament at the time t_{i}, where t_{i} is the number of seconds elapsed since the beginning of the night.

It is known that the freebie is a capricious and willful lady. That night the freebie was near dormitory only for T seconds. Therefore, if for two students their sacrament times differ for more than T, then the freebie didn't visit at least one of them.

Since all students are optimists, they really want to know what is the maximal number of students visited by the freebie can be.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 100), where n — the number of students shouted "Fly, freebie, fly!" The second line contains n positive integers t_{i} (1 ≤ t_{i} ≤ 1000).

The last line contains integer T (1 ≤ T ≤ 1000) — the time interval during which the freebie was near the dormitory.


-----Output-----

Print a single integer — the largest number of people who will pass exam tomorrow because of the freebie visit.


-----Examples-----
Input
6
4 1 7 8 3 8
1

Output
3

Difficulty: MEDIUM
Tags: Sorting

Implementation

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
n = int(input())
t = list(map(int, input().split()))
T = int(input())
t.sort()
m = 1
count = 0
for i in range(n):
	for j in range(i, n):
		if t[j] - t[i] <= T:
			count += 1
	m = max(count, m)
	count = 0
print(m)


import bisect
n = int(input())
arr = sorted(map(int, input().split()))
t = int(input())
res = 0
for i in range(n):
	end = bisect.bisect_right(arr, t + arr[i])
	res = max(res, end - i)
print(res)


def halyava(lst, t):
	count = 1
	for i in range(len(lst)):
		for j in range(i + 1, len(lst)):
			if sorted(lst)[j] - sorted(lst)[i] <= t:
				count = max(j - i + 1, count)
	return count
n = int(input())
b = [int(x) for x in input().split()]
T = int(input())
print(halyava(b, T))


n = int(input())
lst = list(map(int, input().split()))
t = int(input())
lst.sort()
res = 0
from bisect import bisect
for (i, x) in enumerate(lst):
	j = bisect(lst, x + t)
	res = max(res, j - i)
print(res)


n = int(input())
l = [int(i) for i in input().split()]
l.sort()
t = int(input())
st = 0
maxi = 0
for end in range(n):
	while l[end] - l[st] > t:
		st += 1
	if end - st + 1 > maxi:
		maxi = end - st + 1
		ans = (st, end)
print(maxi)


n = int(input())
l = list(map(int, input().split()))
t = int(input())
l.sort()
a = []
i = 0
j = 0
while i < n:
	while j < n and l[j] - l[i] <= t:
		j += 1
	a.append(j - i)
	i += 1
print(max(a))


read = lambda : list(map(int, input().split()))
n = int(input())
a = sorted(read())
T = int(input())
ans = 0
j = 0
for i in range(n):
	while j < n and a[j] - a[i] <= T:
		j += 1
	ans = max(ans, j - i)
print(ans)


(n, t) = (input(), [0] * 1002)
for i in map(int, input().split()):
	t[i] += 1
T = int(input()) + 1
for i in range(1000):
	t[i + 1] += t[i]
print(max((t[i + T] - t[i] for i in range(-1, 1001 - T))))


__author__ = 'asmn'
n = int(input())
a = sorted(map(int, input().split()))
dt = int(input())
(ans, l, r) = (0, 0, 0)
while r < len(a):
	while r < len(a) and a[r] - a[l] <= dt:
		r += 1
	ans = max(ans, r - l)
	l += 1
print(ans)


n = int(input())
lst = sorted(list(map(int, input().split())))
t = int(input())
ans = 1
for i in range(len(lst) - 1):
	temp = 1
	k = i + 1
	while k < len(lst) and lst[k] - lst[i] <= t:
		temp += 1
		k += 1
	if temp > ans:
		ans = temp
print(ans)


n = int(input())
m = list(map(int, input().split()))
t = int(input())
m.sort()
if n == 1 or len(m) == 1:
	print(1)
elif m[-1] - m[0] <= t:
	print(n)
else:
	mx = 1
	for i in range(n - 1):
		ma = 1
		fr = m[i]
		for j in range(i + 1, n):
			if m[j] - fr <= t:
				ma += 1
			else:
				break
		mx = max(ma, mx)
	print(mx)


n = int(input())
l = list(map(int, input().split()))
t = int(input())
l.sort()
mx = 1
i = 0
j = 0
count = 1
while j < n - 1:
	count = 1
	i = j + 1
	while i < n:
		if l[i] - l[j] <= t:
			count += 1
			i += 1
		else:
			break
	if count > mx:
		mx = count
	j += 1
print(mx)


n = int(input())
a = list(map(int, input().split()))
t = int(input())
a.sort()
ans = 0
for i in range(n):
	j = i
	count = 0
	while j < n:
		if a[j] - a[i] <= t:
			count += 1
			j += 1
		else:
			break
	if count > ans:
		ans = count
print(ans)


n = int(input())
L = list(map(int, input().split()))
T = int(input())
X = [0] * 1005
for i in range(len(L)):
	X[L[i]] += 1
for i in range(1, 1005):
	X[i] += X[i - 1]
best = 0
for i in range(1 + T, 1005):
	if X[i] - X[i - T - 1] > best:
		best = X[i] - X[i - T - 1]
print(best)


n = int(input())
l = [int(x) for x in input().split()]
T = int(input())
l.sort()
M = 1
inz = 0
fin = 1
count = 1
while fin < n:
	while fin < n and l[fin] - l[inz] <= T:
		count += 1
		fin += 1
	if count > M:
		M = count
	inz += 1
	count -= 1
	if fin < inz:
		fin = inz
		count = 1
print(M)


n = int(input())
v = list(map(int, input().split()))
t = int(input())
v.sort()
ret = 1
lef = 0
rit = 1
while rit < n:
	while rit < n and v[rit] - v[lef] <= t:
		rit = rit + 1
	ret = max(ret, rit - lef)
	lef = lef + 1
print(ret)


n = int(input())
l = list(map(int, input().split()))
t = int(input())
l.sort()
ans = 0
start = 0
for end in range(n):
	while l[end] - l[start] > t:
		start += 1
	if end - start + 1 > ans:
		ans = end - start + 1
print(ans)


class CodeforcesTask386BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.times = []
		self.t = 0

	def read_input(self):
		self.n = int(input())
		self.times = [int(x) for x in input().split(' ')]
		self.t = int(input())

	def process_task(self):
		result = 0
		self.times.sort()
		for start in set(self.times):
			in_range = 0
			for time in self.times:
				if start <= time <= start + self.t:
					in_range += 1
			result = max(result, in_range)
		self.result = str(result)

	def get_result(self):
		return self.result
Solution = CodeforcesTask386BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


n = int(input())
a = [int(x) for x in input().split()]
t = int(input())
res = 1
a.sort()
for i in range(n):
	for j in range(i + 1, n):
		if a[j] - a[i] <= t:
			res = max(j - i + 1, res)
print(res)


n = int(input())
time = list(map(int, input().split()))
t = int(input())
num = []
time.sort()
tmax = time[-1]
tmin = time[0]
if time[-1] - time[0] <= t:
	print(n)
else:
	la = 0
	stu = 0
	for i in range(n):
		if time[i] <= tmin + t:
			stu += 1
			la = i
		else:
			break
	num.append(stu)
	for i in range(1, n):
		if time[i] + t > tmax:
			break
		if time[i] == time[i - 1]:
			stu -= 1
		else:
			x = time[i] + t
			stu -= 1
			if x <= time[la]:
				break
			else:
				for j in range(la + 1, n):
					if time[j] <= x:
						stu += 1
						la = j
			num.append(stu)
	print(max(num))


n = int(input())
t = sorted(list(map(int, input().split())))
T = int(input())
ans = 0
l = 0
r = 0
while r < n:
	ans = max(ans, r - l + 1)
	if r == n - 1:
		break
	if t[r + 1] - t[l] <= T:
		r += 1
	else:
		l += 1
print(ans)


n = int(input())
p = list(map(int, input().split()))
t = int(input())
p.sort()
ans = 0
i = 0
for j in range(n):
	while p[j] - p[i] > t:
		i = i + 1
	ans = max(ans, j - i + 1)
print(ans)


(n, v) = (int(input()), list(sorted(map(int, input().split()))))
t = int(input())
ans = 0
for i in range(n):
	k = 0
	for j in range(i + 1, n):
		if v[j] - v[i] <= t:
			k += 1
	ans = max(ans, k + 1)
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter
n = int(input())
arr = list(map(int, input().split()))
t = int(input())
arr.sort()
r = 0
l = 0
ans = 0
while r < n:
	while arr[r] - arr[l] > t:
		l += 1
	ans = max(ans, r - l + 1)
	r += 1
print(ans)


n = int(input())
t = list(map(int, input().split()))
tem = int(input())
t.sort()
rmax = 1
for cont in range(0, n - 1):
	r = 1
	for cont2 in range(cont + 1, n):
		if t[cont2] - t[cont] <= tem:
			r += 1
		else:
			break
	if r > rmax:
		rmax = r
print(rmax)


n = int(input())
a = [int(i) for i in input().split()]
k = int(input())
j = 1
x = []
c = 0
g = 0
a.sort()
for i in range(n):
	f = i
	j = i + 1
	g = 0
	c = 0
	while g <= k:
		if j == n:
			break
		if g == k and abs(a[f] - a[j]) != 0:
			break
		elif g + abs(a[f] - a[j]) > k:
			break
		g += abs(a[f] - a[j])
		c += 1
		j += 1
		f += 1
	x.append(c)
print(max(x) + 1)


n = int(input())
p = list(map(int, input().split()))
T = int(input())
p.sort()
fs = 0
maxx = 0
for i in range(n):
	while fs < n and p[fs] - p[i] <= T:
		fs += 1
	maxx = max(maxx, fs - i)
print(maxx)