HackerLand National Bank has a simple policy for warning clients about possible fraudulent account activity. If the amount spent by a client on a particular day is greater than or equal to $2\times$ the client's median spending for a trailing number of days, they send the client a notification about potential fraud. The bank doesn't send the client any notifications until they have at least that trailing number of prior days' transaction data.

Given the number of trailing days $\boldsymbol{d}$ and a client's total daily expenditures for a period of $n$ days, determine the number of times the client will receive a notification over all $n$ days.

Example 

$expenditure=[10,20,30,40]$ 

$\boldsymbol{d}=3$    

On the first three days, they just collect spending data.  At day $4$, trailing expenditures are $[10,20,30]$.  The median is $\textbf{20}$ and the day's expenditure is $\boldsymbol{40}$.  Because $40\geq2\times20$, there will be a notice.  The next day, trailing expenditures are $[20,30,40]$ and the expenditures are $50$.  This is less than $2\times30$ so no notice will be sent.  Over the period, there was one notice sent.

Note: The median of a list of numbers can be found by first sorting the numbers ascending. If there is an odd number of values, the middle one is picked. If there is an even number of values, the median is then defined to be the average of the two middle values. (Wikipedia)

Function Description

Complete the function activityNotifications in the editor below.   

activityNotifications has the following parameter(s):

int expenditure[n]: daily expenditures  
int d: the lookback days for median spending   

Returns    

int: the number of notices sent  

Input Format

The first line contains two space-separated integers $n$ and $\boldsymbol{d}$, the number of days of transaction data, and the number of trailing days' data used to calculate median spending respectively. 

The second line contains $n$ space-separated non-negative integers where each integer $\boldsymbol{i}$ denotes $\textit{expenditure[i]}$.

Constraints

$1\leq n\leq2\times10^5$
$1\leq d\leq n$
$0\leq\textit{expenditure[i]}\leq200$

Output Format

Sample Input 0

STDIN               Function
-----               --------
9 5                 expenditure[] size n =9, d = 5
2 3 4 2 3 6 8 4 5   expenditure = [2, 3, 4, 2, 3, 6, 8, 4, 5]

Sample Output 0

2

Explanation 0

Determine the total number of $notifications$ the client receives over a period of $n=9$ days. For the first five days, the customer receives no notifications because the bank has insufficient transaction data: $notifications=0$. 

On the sixth day, the bank has $\boldsymbol{d}=5$ days of prior transaction data, $\{2,3,4,2,3\}$, and $\textit{median}=3$ dollars. The client spends $\boldsymbol{6}$ dollars, which triggers a notification because $6\geq2\times{median}$: $notifications=0+1=1$. 

On the seventh day, the bank has $\boldsymbol{d}=5$ days of prior transaction data, $\{3,4,2,3,6\}$, and $\textit{median}=3$ dollars. The client spends $8$ dollars, which triggers a notification because $8\geq2\times{median}$:  $notifications=1+1=2$. 

On the eighth day, the bank has $\boldsymbol{d}=5$ days of prior transaction data, $\{4,2,3,6,8\}$, and $median=4$ dollars. The client spends $4$ dollars, which does not trigger a notification because $4<2\times{median}$: $notifications=2$. 

On the ninth day, the bank has $\boldsymbol{d}=5$ days of prior transaction data, $\{2,3,6,8,4\}$, and a transaction median of $4$ dollars. The client spends $5$ dollars, which does not trigger a notification because $5<2\times{median}$: $notifications=2$.

Sample Input 1

5 4
1 2 3 4 4

Sample Output 1

0

There are $4$ days of data required so the first day a notice might go out is day $5$.  Our trailing expenditures are $[1,2,3,4]$ with a median of $2.5$  The client spends $4$ which is less than $2\times2.5$ so no notification is sent.

Source: hackerrank | Difficulty: MEDIUM
Tags: Sorting


Solutions:
from bisect import bisect_left, insort_left
(n, d) = map(int, input().split())
t = list(map(int, input().split()))
noti = 0
lastd = sorted(t[:d])

def med():
	return lastd[d // 2] if d % 2 == 1 else (lastd[d // 2] + lastd[d // 2 - 1]) / 2
for i in range(d, n):
	if t[i] >= 2 * med():
		noti += 1
	del lastd[bisect_left(lastd, t[i - d])]
	insort_left(lastd, t[i])
print(noti)


(n, d) = input().strip().split(' ')
(n, d) = [int(n), int(d)]
moneys = [int(money) for money in input().strip().split(' ')]
notification = 0
med = moneys[:d]

def findIdx(st, ed, v):
	if med[st] == v:
		return st
	if med[ed] == v:
		return ed
	if st == ed or st + 1 == ed:
		return ed
	if med[int((st + ed) / 2)] <= v:
		return findIdx(int((st + ed) / 2), ed, v)
	else:
		return findIdx(st, int((st + ed) / 2), v)
med.sort()
for i in range(d, n):
	if d % 2 == 1:
		m = med[int(d / 2)] * 2
	else:
		m = med[int(d / 2)] + med[int(d / 2) - 1]
	if moneys[i] >= m:
		notification += 1
	del med[findIdx(0, d - 1, moneys[i - d])]
	med.insert(findIdx(0, d - 2, moneys[i]) + 1, moneys[i])
print(notification)


def find_median(freq, d):
	(mid_val, mid_p1_val) = (None, None)
	total = 0
	for (val, count) in enumerate(freq):
		total += count
		if mid_val is None and total >= (d + 1) // 2:
			mid_val = val
		if mid_p1_val is None and total >= (d + 2) // 2:
			mid_p1_val = val
			break
	if d % 2 == 0:
		return (mid_val + mid_p1_val) / 2
	else:
		return mid_val
(n, d) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
freq = [0] * 201
result = 0
for (i, val) in enumerate(a):
	if i >= d and val >= find_median(freq, d) * 2:
		result += 1
	freq[val] += 1
	if i >= d:
		freq[a[i - d]] -= 1
print(result)


import heapq

class Median:

	def __init__(self, cap):
		self.cap = cap
		self.min_pq = []
		self.max_pq = []
		self.all = {}
		self.index = 0
		self.min_pq_len = 0
		self.max_pq_len = 0

	def _clean(self):
		while self.min_pq and self.min_pq[0][2] is None:
			heapq.heappop(self.min_pq)
		while self.max_pq and self.max_pq[0][2] is None:
			heapq.heappop(self.max_pq)

	def add(self, e):
		elem = [e, self.index, [e, False]]
		self.all[self.index] = elem
		self.index += 1
		self._clean()
		if not self.min_pq and (not self.max_pq):
			heapq.heappush(self.min_pq, elem)
			self.min_pq_len += 1
			return
		if e >= self.min_pq[0][2][0]:
			heapq.heappush(self.min_pq, elem)
			self.min_pq_len += 1
		else:
			elem[0] = -e
			elem[2][1] = True
			heapq.heappush(self.max_pq, elem)
			self.max_pq_len += 1
		assert len(self.all) == self.max_pq_len + self.min_pq_len
		if len(self.all) > self.cap:
			index = self.index - self.cap - 1
			y = self.all[index]
			del self.all[index]
			if y[2][1]:
				self.max_pq_len -= 1
			else:
				self.min_pq_len -= 1
			y[2] = None
			self._clean()
		while abs(self.max_pq_len - self.min_pq_len) > 1:
			if self.max_pq_len > self.min_pq_len:
				x = heapq.heappop(self.max_pq)
				x[0] = -x[0]
				x[2][1] = not x[2][1]
				heapq.heappush(self.min_pq, x)
				self.min_pq_len += 1
				self.max_pq_len -= 1
			else:
				x = heapq.heappop(self.min_pq)
				x[0] = -x[0]
				x[2][1] = not x[2][1]
				heapq.heappush(self.max_pq, x)
				self.min_pq_len -= 1
				self.max_pq_len += 1
			self._clean()
		assert len(self.all) == self.max_pq_len + self.min_pq_len

	def median(self):
		assert len(self.all) == self.cap
		self._clean()
		if self.min_pq_len < self.max_pq_len:
			x = self.max_pq[0]
			return x[2][0]
		if self.min_pq_len > self.max_pq_len:
			x = self.min_pq[0]
			return x[2][0]
		x = self.min_pq[0]
		y = self.max_pq[0]
		return (x[2][0] + y[2][0]) / 2
(n, d) = [int(w) for w in input().split()]
days = [int(w) for w in input().split()]
elems = Median(d)
notifications = 0
for i in range(n):
	if i >= d:
		median = elems.median()
		limit = 2 * median
		if days[i] >= limit:
			notifications += 1
	elems.add(days[i])
print(notifications)


def findMedian():
	global dic, med, double
	count = 0
	i = 0
	for i in range(201):
		if i in dic:
			count += dic[i]
		else:
			continue
		if count >= med:
			break
	if not double:
		return i
	if count == med:
		a = i
		i += 1
		while i not in dic:
			i += 1
		return (a + i) / 2
	else:
		return i

def update(remove, add):
	global data, dic
	if remove < 0:
		for i in range(0, add + 1):
			if data[i] not in dic:
				dic[data[i]] = 1
			else:
				dic[data[i]] += 1
		return
	dic[data[remove]] -= 1
	if dic[data[remove]] == 0:
		del dic[data[remove]]
	if data[add] not in dic:
		dic[data[add]] = 1
	else:
		dic[data[add]] += 1
global n, d, data, dic, med, double
(n, d) = list(map(int, input().split()))
data = list(map(int, input().split()))
notifications = 0
double = False
if d % 2 == 0:
	double = True
med = d // 2
if not double:
	med += 1
dic = dict()
for i in range(d, n):
	update(i - d - 1, i - 1)
	median = findMedian()
	median = median * 2
	if data[i] >= median:
		notifications += 1
print(notifications)


import bisect
(n, d) = map(int, input().split())
E = list(map(int, input().split()))
count = 0
B = sorted(E[:d])
for i in range(d, n):
	median = (B[(d - 1) // 2] + B[d // 2]) / 2
	if E[i] >= 2 * median:
		count += 1
	del B[bisect.bisect_left(B, E[i - d])]
	bisect.insort_left(B, E[i])
print(count)


from bisect import bisect, bisect_left
(N, D) = [int(n) for n in input().split()]
nums = [int(n) for n in input().split()]
notifications = 0
L = sorted(nums[:D])

def med(L):
	D = len(L)
	if D % 2 == 1:
		return L[D // 2]
	else:
		return sum(L[D // 2 - 1:D // 2 + 1]) / 2
for n in range(D, N):
	median = med(L)
	L.pop(bisect_left(L, nums[n - D]))
	L.insert(bisect(L, nums[n]), nums[n])
	if nums[n] >= 2 * median:
		notifications += 1
print(notifications)


def part(A, p, k):
	a = p
	b = k
	while a < b:
		while A[a] <= A[p] and a < b:
			a += 1
		while A[b] > A[p] and b > a:
			b -= 1
		if A[a] > A[b]:
			w = A[b]
			A[b] = A[a]
			A[a] = w
			a += 1
			b -= 1
	if A[b] <= A[p]:
		w = A[b]
		A[b] = A[p]
		A[p] = w
	w = A[b - 1]
	A[b - 1] = A[p]
	A[p] = w
	party = b - 1
	return party

def qsort(A, p, k):
	if p < k:
		q = part(A, p, k)
		qsort(A, p, q)
		qsort(A, q + 1, k)

def wstaw(A, el):
	p = 0
	s = len(A)
	k = (p + s) // 2
	while p < s - 1:
		if A[k] > el:
			s = k
		else:
			p = k
		k = (p + s) // 2
	if k > 0:
		A.insert(k + 1, el)
	else:
		A.insert(k, el)
	return A

def dest(A, el):
	p = 0
	s = len(A)
	k = (p + s) // 2
	while A[k] != el:
		if A[k] > el:
			s = k
		else:
			p = k
		k = (p + s) // 2
	del A[k]
	return A

def med(A):
	if not len(A) % 2:
		x = (A[len(A) // 2] + A[(len(A) - 1) // 2]) / 2
	else:
		x = A[len(A) // 2]
	return x
(a, b) = input().strip().split(' ')
(a, b) = [int(a), int(b)]
wart = [int(i) for i in input().strip().split(' ')]
m = wart[0]
dom = wart[0:b]
qsort(dom, 0, b - 1)
ile = 0
for i in range(b, a):
	if wart[i] >= 2 * med(dom):
		ile += 1
	dest(dom, m)
	wstaw(dom, wart[i])
	m = wart[i - b + 1]
print(ile)


(n, d) = input().split(' ')
(n, d) = (int(n), int(d))
exps = [int(exp) for exp in input().split(' ')]
import math
import bisect

def cal_next_window(old_window, remove_value, new_value):
	bisect.insort(old_window, new_value)
	old_window.pop(bisect.bisect(old_window, remove_value) - 1)
	return old_window
half_d = math.floor(d / 2)
fraud_count = 0
window = sorted(exps[0:d])
if d % 2 == 0:
	for i in range(d, n):
		if window[half_d - 1] + window[half_d] <= exps[i]:
			fraud_count += 1
		if i != n - 1:
			window = cal_next_window(window, exps[i - d], exps[i])
else:
	for i in range(d, n):
		if window[half_d] * 2 <= exps[i]:
			fraud_count += 1
		if i != n - 1:
			window = cal_next_window(window, exps[i - d], exps[i])
print(fraud_count)


from collections import deque, Counter
from bisect import insort, bisect_left
from itertools import islice

def RunningMedian(seq, M):
	seq = iter(seq)
	s = []
	m = M // 2
	s = [item for item in islice(seq, M)]
	d = deque(s)
	median = lambda : s[m] if bool(M & 1) else (s[m - 1] + s[m]) * 0.5
	s.sort()
	medians = [median()]
	for item in seq:
		old = d.popleft()
		d.append(item)
		del s[bisect_left(s, old)]
		insort(s, item)
		medians.append(median())
	return medians
(_, window) = map(int, input().split())
expenditures = list(map(int, input().split()))
medians = RunningMedian(expenditures, window)
notifications = 0
for i in range(window, len(expenditures)):
	if expenditures[i] >= 2 * medians[i - window]:
		notifications += 1
print(notifications)


import sys
x = sys.stdin.readlines()
(n, d) = [int(i) for i in x[0].strip().split(' ')]
A = [int(i) for i in x[1].strip().split(' ')]

def bi_s(A, l, r, k):
	if l >= r:
		if A[l] > k:
			return l
		else:
			return l + 1
	while l < r:
		m = (l + (r - 1)) // 2
		if A[m] > k:
			r = m - 1
			return bi_s(A, l, r, k)
		else:
			l = m + 1
			return bi_s(A, l, r, k)
D = [A[0]]
S = 0
for i in range(1, len(A)):
	if len(D) == d:
		if d % 2 and A[i] >= D[d // 2] * 2:
			S = S + 1
		elif not d % 2 and A[i] >= D[d // 2 - 1] + D[d // 2]:
			S = S + 1
		j = bi_s(D, 0, len(D) - 1, A[i - d]) - 1
		D.pop(j)
	j = bi_s(D, 0, len(D) - 1, A[i])
	D.insert(j, A[i])
print(S)


(n, d) = [int(x) for x in input().split()]
e = [int(x) for x in input().split()]
h = [0 for _ in range(200)]
for i in range(d):
	h[e[i]] += 1
total = 0
i = 0
while total < d / 2:
	total += h[i]
	i += 1
mid = i - 1
med = mid
if total == d / 2:
	i = mid + 1
	while not h[i]:
		i += 1
	med = (med + i) / 2
notifications = 0
if e[d] >= 2 * med:
	notifications += 1
for i in range(n - d - 1):
	h[e[i]] -= 1
	h[e[i + d]] += 1
	if e[i] <= med:
		total -= 1
	if e[i + d] <= med:
		total += 1
	if total < d / 2:
		mid += 1
		while not h[mid]:
			mid += 1
		total += h[mid]
	if total - h[mid] >= d / 2:
		total -= h[mid]
		mid -= 1
		while not h[mid]:
			mid -= 1
	med = mid
	if total == d / 2:
		j = mid + 1
		while not h[j]:
			j += 1
		med = (med + j) / 2
	if e[d + i + 1] >= 2 * med:
		notifications += 1
print(notifications)


(n, d) = [int(j) for j in input().split(' ')]
spend = [int(j) for j in input().split(' ')]
alerts = 0
counts = [0] * 201

def median(counts, d):
	if d % 2 == 0:
		sumcounts = 0
		for j in range(201):
			sumcounts += counts[j]
			if sumcounts > d / 2 - 1:
				out = j / 2
				if sumcounts > d / 2:
					out += j / 2
					return out
				else:
					for jj in range(j + 1, 201):
						if counts[jj] > 0:
							out += jj / 2
							return out
	else:
		sumcounts = 0
		for j in range(201):
			sumcounts += counts[j]
			if sumcounts > int(d / 2):
				return j
for day in range(d):
	counts[spend[day]] += 1
for day in range(d, n):
	if spend[day] >= median(counts, d) * 2:
		alerts += 1
	counts[spend[day]] += 1
	counts[spend[day - d]] -= 1
print(alerts)


import bisect
(n, d) = map(int, input().split())
a = list(map(int, input().split()))
even = d % 2 == 0
i1 = d // 2
i2 = i1 - 1
total = 0
window = a[:d]
window.sort()
for (i, j) in zip(range(n - d), range(d, n)):
	med = 0
	if even:
		med = (window[i1] + window[i2]) / 2
	else:
		med = window[i1]
	if a[j] >= med * 2:
		total += 1
	del window[bisect.bisect_left(window, a[i])]
	window.insert(bisect.bisect(window, a[j]), a[j])
print(total)


import bisect
(N, D) = map(int, input().split())
Expens = tuple(map(int, input().split()))
expens_list = []
for idx in range(D):
	bisect.insort_left(expens_list, Expens[idx])
warn_n = 0
(begin, end) = (0, D - 1)
mid = D // 2
while end < N:
	median = (expens_list[mid] + (expens_list[mid] if D & 1 else expens_list[mid - 1])) / 2
	if end + 1 < N:
		if Expens[end + 1] >= 2 * median:
			warn_n += 1
		bisect.insort_left(expens_list, Expens[end + 1])
	expens_list.pop(bisect.bisect_left(expens_list, Expens[begin]))
	begin += 1
	end += 1
print(warn_n)


def medianpar():
	for i in range(201):
		if valpos[i][0] <= d2 - 1 <= valpos[i][1]:
			if d2 <= valpos[i][1]:
				return i
			x = i
			break
	for i in range(x, 201):
		if valpos[i][0] <= d2 <= valpos[i][1]:
			return (x + i) / 2.0

def medianimpar():
	for i in range(201):
		if valpos[i][0] <= d2 <= valpos[i][1]:
			return i

def refreshpos(k):
	if a[k] > a[k - d]:
		if valpos[a[k]][0] <= valpos[a[k]][1]:
			valpos[a[k]][0] -= 1
		else:
			i = 1
			while valpos[a[k] - i][0] > valpos[a[k] - i][1]:
				i += 1
			valpos[a[k]][0] = valpos[a[k]][1] = valpos[a[k] - i][1] + 1
		valpos[a[k - d]][1] -= 1
		for v in range(a[k - d] + 1, a[k]):
			valpos[v][0] -= 1
			valpos[v][1] -= 1
	elif a[k] < a[k - d]:
		if valpos[a[k]][0] <= valpos[a[k]][1]:
			valpos[a[k]][1] += 1
		else:
			i = 1
			while valpos[a[k] + i][0] > valpos[a[k] + i][1]:
				i += 1
			valpos[a[k]][0] = valpos[a[k]][1] = valpos[a[k] + i][0]
		valpos[a[k - d]][0] += 1
		for v in range(a[k] + 1, a[k - d]):
			valpos[v][0] += 1
			valpos[v][1] += 1
(n, d) = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
b = sorted(a[:d])
valpos = [[200, 0] for _ in range(201)]
for i in range(d):
	if i < valpos[b[i]][0]:
		valpos[b[i]][0] = i
	if i > valpos[b[i]][1]:
		valpos[b[i]][1] = i
adv = 0
d2 = d // 2
median = medianpar if d % 2 == 0 else medianimpar
for i in range(d, n):
	if a[i] >= 2 * median():
		adv += 1
	refreshpos(i)
print(adv)


(n, d) = map(int, input().split())
spending = list(map(int, input().split()))
history = [0] * 201
ret = 0
for i in range(d):
	history[spending[i]] += 1

def median(hist):
	seen = 0
	if d % 2:
		for i in range(len(hist)):
			seen += hist[i]
			if seen > d // 2:
				return i
	else:
		for i in range(len(hist)):
			seen += hist[i]
			if d // 2 - seen == 0:
				for nexti in range(i + 1, len(hist)):
					if hist[nexti]:
						return (i + nexti) / 2
			elif seen > d // 2:
				return i
for j in range(d, n):
	if spending[j] >= 2 * median(history):
		ret += 1
	history[spending[j]] += 1
	history[spending[j - d]] -= 1
print(ret)


(n, d) = map(int, input().split())
if d >= n:
	print(0)
else:
	result = 0
	ar = tuple(map(int, input().split()))
	history = [0] * 201
	for i in range(d):
		history[ar[i]] += 1
	m = (d >> 1) + 1
	if d & 1:

		def threshold():
			cumsum = 0
			for i in range(201):
				cumsum += history[i]
				if cumsum >= m:
					return i << 1
	else:

		def threshold():
			cumsum = pre_cs = pre_i = 0
			for i in range(201):
				pre_cs = cumsum
				if history[i]:
					cumsum += history[i]
					if cumsum >= m:
						if pre_cs == m - 1:
							return pre_i + i
						else:
							return i << 1
					pre_i = i
	for i in range(d, n):
		result += ar[i] >= threshold()
		history[ar[i - d]] -= 1
		history[ar[i]] += 1
	print(result)


from bisect import bisect_left, insort
from collections import deque

def running_median(arr, window):
	deq = deque(arr[:window])
	slide = sorted(arr[:window])
	m = window // 2
	median = lambda : slide[m] if bool(window & 1) else (slide[m - 1] + slide[m]) * 0.5
	medians = [median()]
	for item in arr[window:]:
		old = deq.popleft()
		deq.append(item)
		del slide[bisect_left(slide, old)]
		insort(slide, item)
		medians.append(median())
	return medians
(n, d) = map(int, input().split())
arr = [int(x) for x in input().split()]
medians = running_median(arr, d)[:-1]
res = sum((x >= 2 * m for (x, m) in zip(arr[d:], medians)))
print(res)


import statistics
from collections import deque, Counter
from bisect import insort, bisect_left
from itertools import islice
rawInputMeta = input()
rawInputAccountData = input()
rawInputMeta = rawInputMeta.split()
transactionData = rawInputAccountData.split()
transactionData = [int(x) for x in transactionData]
numDays = int(rawInputMeta[0])
priorDaysNeeded = int(rawInputMeta[1])
notifications = 0
seq = iter(transactionData)
s = []
m = priorDaysNeeded // 2
s = [item for item in islice(seq, priorDaysNeeded)]
d = deque(s)
getMedian = lambda : s[m] if bool(priorDaysNeeded & 1) else (s[m - 1] + s[m]) * 0.5
s.sort()
for item in seq:
	a = getMedian()
	fraudCheck = a * 2
	if item >= fraudCheck:
		notifications = notifications + 1
	old = d.popleft()
	d.append(item)
	del s[bisect_left(s, old)]
	insort(s, item)
print(str(notifications))


def odd(c, d):
	l = 0
	while c[l] <= d // 2:
		l += 1
	return 2 * l

def even(c, d):
	l = 0
	while c[l] <= d // 2 - 1:
		l += 1
	r = l
	if c[l] == d // 2:
		k = c[l]
		l += 1
		while l <= 200:
			if c[l] > k:
				r += l
				return r
			l += 1
	else:
		r += l
		return r

def main():
	(n, d) = list(map(int, input().split(' ')))
	e = list(map(int, input().split(' ')))
	c = 201 * [0]
	for i in range(d):
		c[e[i]] += 1
	for j in range(1, 201):
		c[j] += c[j - 1]
	r = 0
	if d % 2 == 0:
		for i in range(d, n):
			if i == d:
				if e[i] >= even(c, d):
					r += 1
			else:
				for j in range(e[i - d - 1], 201):
					c[j] -= 1
				for k in range(e[i - 1], 201):
					c[k] += 1
				if e[i] >= even(c, d):
					r += 1
	else:
		for i in range(d, n):
			if i == d:
				if e[i] >= odd(c, d):
					r += 1
			else:
				for j in range(e[i - d - 1], 201):
					c[j] -= 1
				for k in range(e[i - 1], 201):
					c[k] += 1
				if e[i] >= odd(c, d):
					r += 1
	print(r)
main()


def findValueAtPos(countArr, pos, startIndex=-1, startPos=0):
	currPos = startPos
	index = startIndex
	while currPos < pos:
		index += 1
		currPos += count[index]
	return (index, currPos)

def findMedian(countArr, d):
	medianPos = d // 2 + d % 2
	(median, currPos) = findValueAtPos(countArr, medianPos)
	if d % 2 == 0 and currPos < medianPos + 1:
		median = (median + findValueAtPos(countArr, medianPos + 1, median, currPos)[0]) / 2.0
	return median
(n, d) = [int(i) for i in input().split(' ')]
expanditure = [int(i) for i in input().split(' ')]
count = [0] * 200
for i in range(d):
	count[expanditure[i]] += 1
median = findMedian(count, d)
alerts = 0
for i in range(d, n - 1):
	newVal = expanditure[i]
	oldVal = expanditure[i - d]
	count[oldVal] -= 1
	count[newVal] += 1
	if newVal >= 2 * median:
		alerts += 1
	if i == n - 1:
		break
	if newVal > median and oldVal <= median or (newVal < median and oldVal >= median):
		median = findMedian(count, d)
print(alerts)


import bisect
(n, d) = map(int, input().split())
fullList = list(map(int, input().split()))
current = []
alerts = 0
for i in range(n):
	number = fullList[i]
	if i - d >= 0:
		median = None
		if len(current) % 2 == 1:
			median = current[int(len(current) / 2)]
		else:
			median = (current[int(len(current) / 2) - 1] + current[int(len(current) / 2)]) / 2
		if number >= median * 2:
			alerts += 1
		toRemove = fullList[i - d]
		index = bisect.bisect_left(current, toRemove)
		del current[index]
	bisect.insort_left(current, number)
print(alerts)


def getMedian(ar, d):
	x = (d + 1) // 2
	add = 0
	index = -1
	for i in range(201):
		add += ar[i]
		if add >= x:
			index = i
			break
	if d & 1 == 1:
		return index
	elif add == x:
		index1 = index
		for j in range(index + 1, 201):
			if ar[i] > 0:
				return (index1 + j) / 2
	else:
		return index
(n, d) = map(int, input().split())
st = list(map(int, input().split()))
res = 0
ar = [0 for i in range(201)]
for i in range(d):
	ar[st[i]] += 1
i = 0
j = d
for j in range(d, n):
	x = getMedian(ar, d)
	if 2 * x <= st[j]:
		res += 1
	ar[st[i]] -= 1
	ar[st[j]] += 1
	i += 1
print(res)


import random
days = [int(x) for x in input().split(' ')]
money = [int(x) for x in input().split(' ')]
exp = [0] * 201
notif = 0
for i in range(days[1]):
	exp[money[i]] += 1
pos = 0
lim = days[1]

def find_median_odd():
	target = days[1] // 2
	i = -1
	while target > -1:
		i += 1
		target -= exp[i]
	return i

def find_median_even():
	target = days[1] // 2
	i = -1
	while target > -1:
		i += 1
		target -= exp[i]
	part1 = i
	target = days[1] // 2 - 1
	i = -1
	while target > -1:
		i += 1
		target -= exp[i]
	part2 = i
	return (part1 + part2) / 2
median = find_median_odd
if days[1] % 2 == 0:
	median = find_median_even
for i in range(days[1], days[0]):
	med = median()
	if money[i] >= med * 2:
		notif += 1
	exp[money[pos]] -= 1
	exp[money[lim]] += 1
	pos += 1
	lim += 1
print(notif)


import bisect
(n, d) = map(int, input().strip().split(' '))
purchases = [int(s) for s in input().strip().split(' ')]
count = 0
if d < len(purchases):
	days = sorted(purchases[0:d])
	med_i = d // 2
	med_is_odd = d % 2 == 1
	if med_is_odd:
		med = days[med_i]
	else:
		med = sum(days[med_i - 1:med_i + 1]) / 2
	for i in range(d, len(purchases)):
		current_el = purchases[i]
		if current_el >= med * 2:
			count += 1
		if i < len(purchases) - 1:
			if purchases[i - d] == current_el:
				continue
			days.pop(bisect.bisect_left(days, purchases[i - d]))
			bisect.insort_left(days, current_el)
			if med_is_odd:
				med = days[med_i]
			else:
				med = sum(days[med_i - 1:med_i + 1]) / 2
print(count)


a = [0] * 201
(n, d) = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
nots = 0
for i in l[:d]:
	a[i] += 1

def median(a, d):
	sum = 0
	sum1 = 0
	if d % 2 == 1:
		for i in range(len(a)):
			sum += a[i]
			if d // 2 + 1 <= sum:
				return i
	else:
		for i in range(len(a)):
			if i != 0:
				sum1 += a[i - 1]
			sum += a[i]
			if d // 2 + 1 <= sum:
				(t, t2) = (i, i - 1)
				while t2:
					if a[t2] != 0:
						break
					t2 -= 1
				if a[t] == 1 or d // 2 + 1 - sum1 == 1:
					return (t + t2) / 2
				else:
					return float(t)
for i in range(len(l[d:])):
	med = median(a, d)
	if l[i + d] >= 2 * med:
		nots += 1
	a[l[i]] -= 1
	a[l[i + d]] += 1
print(nots)


class MinHeap:

	def __init__(self, iterable=(), comparator=lambda a, b: a < b):
		self._comparator = comparator
		self._len = 0
		self._heap = []
		self._counts = []
		self._heap_index = {}
		for item in iterable:
			if item in self._heap_index:
				self._counts[self._heap_index[item]] += 1
			else:
				self._heap.append(item)
				self._counts.append(1)
			self._len += 1
		self._heapify()

	def __len__(self):
		return self._len

	def __contains__(self, item):
		return item in self._heap_index

	def __repr__(self):
		return '<MinHeap heap={heap!r}, counts={counts!r}>'.format(**{'heap': self._heap, 'counts': self._counts})

	def push(self, item):
		if item in self._heap_index:
			self._counts[self._heap_index[item]] += 1
		else:
			new_item_index = len(self._heap)
			self._heap.append(item)
			self._counts.append(1)
			self._heap_index[item] = new_item_index
			self._bubble_up(new_item_index)
		self._len += 1

	def peek(self):
		return self._heap[0]

	def pop(self):
		front = self.peek()
		self.remove(front)
		return front

	def remove(self, item):
		item_index = self._heap_index[item]
		self._len -= 1
		self._counts[item_index] -= 1
		if self._counts[item_index] > 0:
			return
		self._swap(item_index, len(self._heap) - 1)
		self._heap.pop()
		self._counts.pop()
		del self._heap_index[item]
		if item_index < len(self._heap):
			if self._comparator(self._heap[item_index], item):
				self._bubble_up(item_index)
			else:
				self._bubble_down(item_index)

	def _swap(self, i, j):
		if i != j:
			(self._heap[i], self._heap[j]) = (self._heap[j], self._heap[i])
			(self._counts[i], self._counts[j]) = (self._counts[j], self._counts[i])
			self._heap_index[self._heap[i]] = i
			self._heap_index[self._heap[j]] = j

	def _bubble_down(self, i):
		while True:
			least_i = i
			for poss_i in range(2 * i + 1, min(2 * i + 3, len(self._heap))):
				if self._comparator(self._heap[poss_i], self._heap[least_i]):
					least_i = poss_i
			if least_i == i:
				break
			self._swap(i, least_i)
			i = least_i

	def _bubble_up(self, i):
		while i > 0:
			parent_i = (i - 1) // 2
			if not self._comparator(self._heap[i], self._heap[parent_i]):
				break
			self._swap(parent_i, i)
			i = parent_i

	def _heapify(self):
		for i in range((len(self._heap) - 2) // 2, -1, -1):
			self._bubble_down(i)

class RunningMedian:

	def __init__(self):
		self._greater_half = MinHeap()
		self._lesser_half = MinHeap(comparator=lambda a, b: b < a)

	def __len__(self):
		return len(self._greater_half) + len(self._lesser_half)

	def __contains__(self, item):
		return item in self._greater_half or item in self._lesser_half

	def __repr__(self):
		return '<RunningMedian lesser_half={lesser_half!r}, greater_half={greater_half!r}>'.format(**{'lesser_half': self._lesser_half, 'greater_half': self._greater_half})

	def push(self, item):
		if len(self._greater_half) > 0 and self._greater_half.peek() < item:
			self._greater_half.push(item)
		elif len(self._lesser_half) > 0 and item < self._lesser_half.peek():
			self._lesser_half.push(item)
		elif len(self._lesser_half) < len(self._greater_half):
			self._lesser_half.push(item)
		else:
			self._greater_half.push(item)

	def remove(self, item):
		if item in self._greater_half and item in self._lesser_half:
			if len(self._lesser_half) < len(self._greater_half):
				self._greater_half.remove(item)
			else:
				self._lesser_half.remove(item)
		elif item in self._greater_half:
			self._greater_half.remove(item)
		else:
			self._lesser_half.remove(item)

	def balance(self):
		while len(self._greater_half) < len(self._lesser_half):
			self._greater_half.push(self._lesser_half.pop())
		while len(self._lesser_half) + 1 < len(self._greater_half):
			self._lesser_half.push(self._greater_half.pop())

	def median(self):
		self.balance()
		med = self._greater_half.peek()
		if len(self._lesser_half) == len(self._greater_half):
			med = (med + self._lesser_half.peek()) / 2
		return med
(n, d) = (int(x) for x in input().strip().split())
arr = [int(x) for x in input().strip().split()]
running_median = RunningMedian()
count = 0
for i in range(len(arr)):
	if d <= i:
		if 2 * running_median.median() <= arr[i]:
			count += 1
		running_median.remove(arr[i - d])
	running_median.push(arr[i])
print(count)


from bisect import insort, bisect_left
(n, d) = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
num_notifications = 0
b = sorted(a[0:d])
for i in range(d, n):
	if d % 2 == 1:
		thresh = 2 * b[d // 2]
	else:
		thresh = b[d // 2] + b[d // 2 - 1]
	if a[i] >= thresh:
		num_notifications += 1
	del b[bisect_left(b, a[i - d])]
	insort(b, a[i])
print(num_notifications)


import sys

def get_median(A, count):
	target = count // 2
	if count % 2 == 1:
		target += 1
	seen = 0
	for val in range(len(A)):
		seen += A[val]
		if seen >= target:
			if count % 2 == 1 or seen > target:
				return val
			else:
				first = val
				second = first + 1
				while A[second] == 0:
					second += 1
				return (first + second) / 2
(n, d) = map(int, input().split())
exp = list(map(int, input().split()))
A = [0] * 201
for i in range(d):
	A[exp[i]] += 1
front = d
back = 0
res = 0
while front < len(exp):
	if exp[front] >= 2 * get_median(A, d):
		res += 1
	A[exp[front]] += 1
	A[exp[back]] -= 1
	front += 1
	back += 1
print(res)


import statistics
from random import random
from math import log, ceil

class Node(object):
	__slots__ = ('value', 'next', 'width')

	def __init__(self, value, next, width):
		(self.value, self.next, self.width) = (value, next, width)

class End(object):

	def __le__(self, other):
		return 0

	def __lt__(self, other):
		return 0

	def __eq__(self, other):
		return 0
NIL = Node(End(), [], [])

class IndexableSkiplist:

	def __init__(self, expected_size=100):
		self.size = 0
		self.maxlevels = int(1 + log(expected_size, 2))
		self.head = Node('HEAD', [NIL] * self.maxlevels, [1] * self.maxlevels)

	def __len__(self):
		return self.size

	def __getitem__(self, i):
		node = self.head
		i += 1
		for level in reversed(range(self.maxlevels)):
			while node.width[level] <= i:
				i -= node.width[level]
				node = node.next[level]
		return node.value

	def insert(self, value):
		chain = [None] * self.maxlevels
		steps_at_level = [0] * self.maxlevels
		node = self.head
		for level in reversed(range(self.maxlevels)):
			while node.next[level].value <= value:
				steps_at_level[level] += node.width[level]
				node = node.next[level]
			chain[level] = node
		d = min(self.maxlevels, 1 - int(log(random(), 2.0)))
		newnode = Node(value, [None] * d, [None] * d)
		steps = 0
		for level in range(d):
			prevnode = chain[level]
			newnode.next[level] = prevnode.next[level]
			prevnode.next[level] = newnode
			newnode.width[level] = prevnode.width[level] - steps
			prevnode.width[level] = steps + 1
			steps += steps_at_level[level]
		for level in range(d, self.maxlevels):
			chain[level].width[level] += 1
		self.size += 1

	def remove(self, value):
		chain = [None] * self.maxlevels
		node = self.head
		for level in reversed(range(self.maxlevels)):
			while node.next[level].value < value:
				node = node.next[level]
			chain[level] = node
		if value != chain[0].next[0].value:
			raise KeyError('Not Found')
		d = len(chain[0].next[0].next)
		for level in range(d):
			prevnode = chain[level]
			prevnode.width[level] += prevnode.next[level].width[level] - 1
			prevnode.next[level] = prevnode.next[level].next[level]
		for level in range(d, self.maxlevels):
			chain[level].width[level] -= 1
		self.size -= 1

	def __iter__(self):
		node = self.head.next[0]
		while node is not NIL:
			yield node.value
			node = node.next[0]
from collections import deque
from itertools import islice

class RunningMedian:

	def __init__(self, n, iterable):
		self.it = iter(iterable)
		self.queue = deque(islice(self.it, n))
		self.skiplist = IndexableSkiplist(n)
		for elem in self.queue:
			self.skiplist.insert(elem)

	def __iter__(self):
		queue = self.queue
		skiplist = self.skiplist
		midpoint = len(queue) // 2
		midpoint_2 = (len(queue) - 1) // 2
		if midpoint != midpoint_2:
			yield ((skiplist[midpoint] + skiplist[midpoint_2]) / 2)
		else:
			yield skiplist[midpoint]
		for newelem in self.it:
			oldelem = queue.popleft()
			skiplist.remove(oldelem)
			queue.append(newelem)
			skiplist.insert(newelem)
			if midpoint != midpoint_2:
				yield ((skiplist[midpoint] + skiplist[midpoint_2]) / 2)
			else:
				yield skiplist[midpoint]
(_, d) = input().split()
d = int(d)
arr = [int(a) for a in input().split()]
rm = list(RunningMedian(d, arr))
print(len([a for (a, b) in zip(rm[:-1], arr[d:]) if 2 * a <= b]))


(n, d) = map(int, input().strip().split(' '))
exps = [int(i) for i in input().strip().split(' ')]

def median(l):
	if len(l) % 2 == 1:
		return l[len(l) // 2]
	else:
		return (l[len(l) // 2] + l[len(l) // 2 + 1]) / 2
notifications = 0
hist = [0] * 201
for i in exps[0:d]:
	hist[i] += 1
for i in range(d, n):
	m = 0.0
	if d % 2 != 0:
		days = 0
		for j in range(201):
			days += hist[j]
			if days >= d // 2 + 1:
				m = float(j)
				break
	else:
		days = 0
		m1 = 0
		m2 = 0
		for j in range(201):
			days += hist[j]
			if days >= d // 2 and m1 == 0.0:
				m1 = float(j)
			if days > d // 2 and m2 == 0.0:
				m2 = float(j)
			if m1 != 0.0 and m2 != 0.0:
				m = (m1 + m2) / 2
				break
	if exps[i] >= 2 * m:
		notifications += 1
	hist[exps[i - d]] -= 1
	hist[exps[i]] += 1
print(notifications)


(n, d) = list(map(int, input().strip().split()))
ar = list(map(int, input().strip().split()))

def findMedian(counts, d):
	csum = 0
	med1 = None
	for (val, count) in enumerate(counts):
		csum += count
		if med1 is None and csum >= d // 2:
			med1 = val
		if csum >= d // 2 + 1:
			med2 = val
			break
	median = med2
	if d % 2 == 0:
		median = 0.5 * (med1 + med2)
	return median
counts = [0] * 201
for val in ar[0:d]:
	counts[val] += 1
notifications = 0
for i in range(d, n):
	if ar[i] >= 2 * findMedian(counts, d):
		notifications += 1
	counts[ar[i - d]] -= 1
	counts[ar[i]] += 1
print(notifications)


from array import array
from bisect import bisect, insort

def median(x):
	return (x[h] + x[~h]) / 2
(n, d) = [int(x) for x in input().split()]
h = d // 2
arr = [int(x) for x in input().split()]
values = array('i', sorted(arr[:d]))
notifications = 0
for (i, v) in enumerate(arr[d:]):
	if v >= median(values) * 2:
		notifications += 1
	p = bisect(values, arr[i])
	del values[p - 1]
	insort(values, v)
print(notifications)


(days, sample_days) = [int(i) for i in input().split()]
exp = [int(i) for i in input().split()]
noti = 0
w = [0] * 201
for i in range(sample_days):
	w[exp[i]] += 1
for i in range(days - sample_days):
	(index, low, high) = (0, 0, 0)
	if sample_days % 2 == 1:
		for j in range(201):
			index += w[j]
			if index >= sample_days // 2 + 1:
				med = j * 2
				break
	else:
		for j in range(201):
			index += w[j]
			if index >= sample_days // 2 and low == 0:
				low = j
			if index >= sample_days // 2 + 1 and high == 0:
				high = j
			if low != 0 and high != 0:
				med = low + high
				break
	if exp[i + sample_days] >= med:
		noti += 1
	w[exp[i]] -= 1
	w[exp[i + sample_days]] += 1
print(noti)


import bisect

def median(a):
	l = len(a)
	if l % 2 == 0:
		h = l // 2
		return (a[h - 1] + a[h]) / 2
	else:
		return a[l // 2]
(n, d) = list(map(int, input().split()))
array = list(map(int, input().split()))
number = 0
current = []
for (i, el) in enumerate(array):
	if d > len(current):
		bisect.insort_left(current, el)
	elif d == len(current):
		med = median(current)
		if el >= 2 * med:
			number += 1
		current.pop(bisect.bisect_left(current, array[i - d]))
		bisect.insort_left(current, el)
print(number)


from collections import defaultdict

class IndexedMinHeap:

	def __init__(self, *args, key=None):

		def identity(x):
			return x
		self.heap = []
		self.index = defaultdict(set)
		if key is None:
			self.key_fn = identity
		else:
			self.key_fn = key

	def __contains__(self, item):
		return bool(self.index.get(item))

	def __len__(self):
		return len(self.heap)

	def parent(self, i):
		return (i - 1) // 2

	def left(self, i):
		return 2 * i + 1

	def right(self, i):
		return 2 * i + 2

	def key(self, i):
		return self.key_fn(self.heap[i])

	def swap(self, i, j, verbose=False):
		if i == j:
			return
		old_i = self.heap[i]
		old_j = self.heap[j]
		old_i_index = self.index[old_i]
		old_j_index = self.index[old_j]
		old_i_index.remove(i)
		old_j_index.remove(j)
		old_i_index.add(j)
		old_j_index.add(i)
		self.heap[i] = old_j
		self.heap[j] = old_i

	def push(self, item):
		i = len(self.heap)
		self.index[item].add(i)
		self.heap.append(item)
		self.bubble_up(i)

	def pop(self):
		if not self.heap:
			raise IndexError('pop called on empty heap')
		last = len(self.heap) - 1
		self.swap(0, last)
		item = self.heap.pop()
		self.index[item].remove(last)
		if len(self.index[item]) == 0:
			del self.index[item]
		self.bubble_down(0)
		return item

	def peek(self):
		return self.heap[0]

	def update(self, old, new):
		i = self.index[old].pop()
		old_key = self.key(old)
		new_key = self.key(new)
		self.index[new].add(i)
		if new_key < old_key:
			self.bubble_up(i)
		elif new_key > old_key:
			self.bubble_down(i)

	def get_index(self, item):
		try:
			i = next(iter(self.index[item]))
			return i
		except StopIteration:
			pass
		raise KeyError(self.key(item))

	def remove(self, item):
		i = self.get_index(item)
		last = len(self.heap) - 1
		self.swap(i, last)
		self.heap.pop()
		self.index[item].remove(last)
		if len(self.index[item]) == 0:
			del self.index[item]
		if 0 < i < len(self.heap) and self.key(i) < self.key(self.parent(i)):
			self.bubble_up(i)
		else:
			self.bubble_down(i)

	def bubble_down(self, i):
		while True:
			l = self.left(i)
			r = l + 1
			smallest = i
			if l < len(self.heap) and self.key(l) < self.key(smallest):
				smallest = l
			if r < len(self.heap) and self.key(r) < self.key(smallest):
				smallest = r
			if smallest == i:
				break
			self.swap(i, smallest)
			i = smallest

	def bubble_up(self, i):
		parent = self.parent(i)
		while i != 0 and self.key(i) < self.key(parent):
			self.swap(i, parent)
			i = parent
			parent = self.parent(i)

class MedianHeap:

	def __init__(self):
		self.min_heap = IndexedMinHeap()
		self.max_heap = IndexedMinHeap(key=lambda x: -x)

	def push(self, item):
		try:
			median = self.median()
		except IndexError:
			self.min_heap.push(item)
			return
		if item >= median:
			self.min_heap.push(item)
			if len(self.min_heap) > len(self.max_heap) + 1:
				self.max_heap.push(self.min_heap.pop())
		else:
			self.max_heap.push(item)
			if len(self.max_heap) > len(self.min_heap) + 1:
				self.min_heap.push(self.max_heap.pop())

	def median(self):
		min_size = len(self.min_heap)
		max_size = len(self.max_heap)
		if min_size > max_size:
			return self.min_heap.peek()
		elif min_size < max_size:
			return self.max_heap.peek()
		else:
			return (self.min_heap.peek() + self.max_heap.peek()) / 2

	def remove(self, item):
		if item in self.min_heap:
			self.min_heap.remove(item)
			if len(self.max_heap) > len(self.min_heap) + 1:
				self.min_heap.push(self.max_heap.pop())
		elif item in self.max_heap:
			self.max_heap.remove(item)
			if len(self.min_heap) > len(self.max_heap) + 1:
				self.max_heap.push(self.min_heap.pop())
		else:
			raise KeyError(item)
(n, d) = [int(s) for s in input().strip().split()]
expenditures = [int(s) for s in input().strip().split()]
alerts = 0
median_heap = MedianHeap()
for expenditure in expenditures[:d]:
	median_heap.push(expenditure)
for i in range(d, n):
	m = median_heap.median()
	alert = expenditures[i] >= m * 2
	if alert:
		alerts += 1
	median_heap.remove(expenditures[i - d])
	median_heap.push(expenditures[i])
print(alerts)


(n, d) = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
w = [0] * 201
for i in range(d):
	w[a[i]] += 1
c = 0
if d % 2 != 0:
	m = (d + 1) // 2
	for i in range(n - d):
		mi = 0
		for j in range(201):
			mi += w[j]
			if mi >= m:
				mv = j
				break
		if a[d + i] >= mv * 2:
			c += 1
		w[a[i]] -= 1
		w[a[d + i]] += 1
else:
	m = d // 2
	for i in range(n - d):
		(mi, li, lo) = (0, 0, 0)
		for j in range(201):
			mi += w[j]
			if mi >= m and li == 0:
				li = j
			if mi >= m + 1 and lo == 0:
				lo = j
			if li != 0 and lo != 0:
				mv = (li + lo) / 2
				break
		if a[d + i] >= mv * 2:
			c += 1
		w[a[i]] -= 1
		w[a[d + i]] += 1
print(c)


__author__ = 'chrisgreening'
import statistics
import bisect
(n, d) = [int(x.strip()) for x in input().split(' ')]
e = [int(x.strip()) for x in input().split(' ')]
total = 0
sorted = e[0:d]
sorted.sort()

def del_element(x):
	del sorted[bisect.bisect_left(sorted, x)]

def add_element(x):
	bisect.insort(sorted, x)

def get_media():
	if d % 2 == 0:
		return (sorted[d // 2] + sorted[d // 2 - 1]) / 2
	return sorted[d // 2]
if d < n and d >= 1:
	for i in range(d, n):
		m = get_media()
		if e[i] >= 2 * m:
			total += 1
		del_element(e[i - d])
		add_element(e[i])
print(total)


(n, d) = [int(temp) for temp in input().split(' ')]
arr = [int(temp) for temp in input().split(' ')]
assert len(arr) == n
notifications = 0
expenditures = [0] * 201
median_idx1 = (d + 1) // 2
median_idx2 = (d + 2) // 2
for i in range(d):
	expenditures[arr[i]] += 1
for i in range(d, n):
	count = 0
	j = 0
	median = 0
	median1 = -1
	median2 = -1
	while j < 201:
		count += expenditures[j]
		if median1 == -1 and count >= median_idx1:
			median1 = j
		if count >= median_idx2:
			median2 = j
			break
		j += 1
	median = (median1 + median2) / 2
	expenditures[arr[i]] += 1
	expenditures[arr[i - d]] -= 1
	if 2 * median <= arr[i]:
		notifications += 1
print(notifications)


from collections import Counter

def calcmed(cn, d, sp):
	(cml, ix) = (0, 0)
	flox = sorted(cn.items())
	while cml < d - cml:
		(cml, ix) = (cml + flox[ix][1], ix + 1)
	if cml == d - cml:
		md = flox[ix][0] + flox[ix - 1][0]
	else:
		md = 2 * flox[ix - 1][0]
	return 1 if sp >= md else 0
(n, d) = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
noti = 0
cn = Counter(A[:d])
for j in range(d, len(A)):
	noti += calcmed(cn, d, A[j])
	cn[A[j - d]] -= 1
	cn[A[j]] += 1
print(noti)


import sys

def med_points(C, lm, rm):
	k = 0
	lo = C[k]
	while lo <= lm:
		lo += C[k + 1]
		k += 1
	j = k
	while lo <= rm:
		lo += C[j + 1]
		j += 1
	return (k, j)
(n, d) = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
C = [0 for _ in range(201)]
for i in range(d):
	C[A[i]] += 1
rm = int(d / 2)
lm = rm
if d % 2 == 0:
	lm -= 1
(k, j) = med_points(C, lm, rm)
count = 0
for i in range(d, n):
	if A[i] >= k + j:
		count += 1
	C[A[i - d]] -= 1
	C[A[i]] += 1
	if A[i - d] <= k and A[i] <= k or (A[i - d] >= j and A[i] >= j):
		continue
	else:
		(k, j) = med_points(C, lm, rm)
print(str(count))


def find_median_doubled():
	tmp = 0
	i = -1
	while tmp + count[i + 1] <= d / 2:
		tmp += count[i + 1]
		i += 1
	if tmp < d / 2:
		return 2 * i + 2
	else:
		return 2 * i + 1
(n, d) = map(int, input().split())
e = list(map(int, input().split()))
count = [0] * 201
alarm = 0
for i in range(d):
	count[e[i]] += 1
for i in range(d, n):
	if e[i] >= find_median_doubled():
		alarm += 1
	count[e[i - d]] -= 1
	count[e[i]] += 1
print(alarm)


(n, d) = input().split(' ')
(n, d) = (int(n), int(d))
exp = [int(e) for e in input().split(' ')]
tracker = [0] * 201
over_med = 0
for i in range(d):
	daily_exp = exp[i]
	tracker[daily_exp] += 1

def find_index(days, arr):
	days += 1
	i = 0
	while i < 201:
		days -= arr[i]
		if days <= 0:
			return i
		i += 1
for k in range(d, len(exp)):
	ind_remove = k - d
	num_remove = exp[ind_remove]
	ind_add = k
	num_add = exp[ind_add]
	if d % 2 == 0:
		med1 = find_index(d / 2, tracker)
		med2 = find_index(d / 2 - 1, tracker)
		med = (med1 + med2) / 2
	else:
		med = find_index(int(d / 2), tracker)
	if num_add >= med * 2:
		over_med += 1
	tracker[num_remove] -= 1
	tracker[num_add] += 1
print(over_med)


(n, d) = [int(i) for i in input().split(' ')]
A = [int(i) for i in input().split(' ')]
iMedian = d // 2
B = [0] * 201
for i in range(d):
	B[A[i]] += 1
count = 0
for i in range(d, n):
	if d % 2 != 0:
		iTotal = 0
		for j in range(201):
			iTotal += B[j]
			if iTotal >= iMedian + 1:
				break
		median = j
		if median * 2 <= A[i]:
			count += 1
	else:
		iTotal = 0
		for j in range(201):
			iTotal += B[j]
			if iTotal >= iMedian:
				break
		median = j
		if iTotal == iMedian:
			j += 1
			while B[j] == 0:
				j += 1
			median = (median + j) / 2
		if median * 2 <= A[i]:
			count += 1
	B[A[i - d]] -= 1
	B[A[i]] += 1
print(count)


from collections import Counter
import gc

def getFraudNotifications2(k, exp, max_range):
	if k >= len(exp):
		return 0
	records = Counter(exp[:k])
	result = 0
	[med, med_index, med_index_count] = getMedian2(records)
	for i in range(k, len(exp)):
		if exp[i] >= 2 * med:
			result += 1
		[med, med_index, med_index_count] = updateRecords(records, med, med_index, med_index_count, exp[i], exp[i - k], k)
	return result

def updateRecords(records, med, med_index, med_index_count, new_val, old_val, capacity):
	new_med = med_index
	new_med_index_count = med_index_count
	old_low = med_index
	old_hi = med_index
	if capacity % 2 == 0 and med_index_count == 0:
		old_low = prevIndex(records, med_index)
	if new_val not in records:
		records[new_val] = 1
	else:
		records[new_val] = records[new_val] + 1
	records[old_val] = records[old_val] - 1
	return getMedian2(records)
	if capacity % 2:
		return [new_med, new_med, new_med_index_count]
	elif new_med_index_count:
		return [new_med, new_med, new_med_index_count]
	else:
		lower = prevIndex(records, new_med)
		return [(lower + new_med) / 2, new_med, 0]

def prevIndex(record, med):
	result = med - 1
	while result not in record or record[result] == 0:
		print('prev', result, record, med)
		result -= 1
	return result

def nextIndex(record, med):
	result = med + 1
	while result not in record or record[result] == 0:
		result += 1
	return result

def getMedian2(counter):
	s = sum(counter.values())
	target = s // 2
	med_index = 0
	med_index_count = 0
	for i in range(max(counter.keys()) + 1):
		if i in counter:
			if counter[i] > target:
				med_index = i
				med_index_count = target
				break
			else:
				target -= counter[i]
	if s % 2:
		return [med_index, med_index, med_index_count]
	elif med_index_count:
		return [med_index, med_index, med_index_count]
	else:
		lower = prevIndex(counter, med_index)
		return [(lower + med_index) / 2, med_index, 0]

def getFraudNotifications(k, exp):
	if k >= len(exp):
		return 0
	result = 0
	records = [[exp[i], i] for i in range(k)]
	records.sort()
	for i in range(k, len(exp)):
		if i % 1000 == 0:
			print('progress', i)
		if exp[i] > getMedian(records):
			result += 1
		start = 0
		while records[start][1] != i - k and records[start][0] <= exp[i]:
			start += 1
		if records[start][1] == i - k:
			while start < k - 1 and records[start + 1][0] < exp[i]:
				records[start] = records[start + 1]
				start += 1
			records[start] = [exp[i], i]
		else:
			new_r = [exp[i], i]
			while records[start][1] != i - k:
				temp = records[start]
				records[start] = new_r
				new_r = temp
				start += 1
			records[start] = new_r
	return result

def getMedian(ar):
	d = len(ar)
	if d % 2:
		return ar[d // 2][0]
	else:
		return (ar[d // 2][0] + ar[(d - 1) // 2][0]) / 2
[n, k] = [int(i) for i in input().split()]
exp = [int(i) for i in input().split()]
gc.disable()
fraud_count = getFraudNotifications2(k, exp, 200)
gc.enable()
print(fraud_count)


import math
PRINT = False
MAX_EXP = 200
(n, d) = input().strip().split(' ')
[n, d] = [int(n), int(d)]
expenditure = input().strip().split(' ')
expenditure = list(map(int, expenditure))

def print_array(ar):
	print(' '.join(map(str, ar)))

def countingSort(ar):
	aux_ar = [0 for a in range(MAX_EXP + 1)]
	for val in ar:
		aux_ar[val] += 1
	index = 0
	countingSort_from_aux(aux_ar, ar)
	return aux_ar

def countingSort_from_aux(aux_ar, ar):
	index = 0
	for (idx, val) in enumerate(aux_ar):
		for i in range(val):
			ar[index] = idx
			index += 1

def median(aux_ar, length):
	middle1 = length // 2
	middle2 = length // 2
	if length % 2 == 0:
		middle1 = length // 2 - 1
		middle2 = length // 2
	if PRINT:
		print('M1: ' + str(middle1))
		print('M2: ' + str(middle2))
	index = 0
	while 0 <= middle1:
		middle1 -= aux_ar[index]
		middle2 -= aux_ar[index]
		index += 1
	med1 = index - 1
	while 0 <= middle2:
		middle2 -= aux_ar[index]
		index += 1
	med2 = index - 1
	median = (med1 + med2) / 2
	if PRINT:
		print('Me1: ' + str(med1))
		print('Me2: ' + str(med2))
		print('Med: ' + str(median))
		print('-------------------')
	return median

def median_old(ar):
	length = len(ar)
	middle1 = math.floor(length / 2)
	middle2 = math.ceil(length / 2)
	if length % 2 != 0:
		middle1 = length // 2
		middle2 = length // 2
	med1 = ar[middle1]
	med2 = ar[middle2]
	median = (med1 + med2) // 2
	return median

def add_sorted(ar, elem):
	i = find_position_sorted(ar, elem, 0, len(ar))
	return (ar[:i] + [elem] + ar[i:], i)

def find_position_sorted(ar, elem, ini, end):
	i_mid = math.floor(len(ar[ini:end]) / 2) + ini
	if ar[i_mid] == elem:
		return i_mid
	elif ini + 1 == end and ar[i_mid] < elem:
		return i_mid + 1
	elif ini + 1 == end and ar[i_mid] > elem:
		return i_mid
	elif ar[i_mid] < elem:
		return find_position_sorted(ar, elem, i_mid + 1, end)
	elif ar[i_mid] > elem:
		return find_position_sorted(ar, elem, ini, i_mid)
i_inserted = None
i = d - 1
ini = i - d + 1
notifications = 0
comp_median = expenditure[ini:i + 1]
aux_ar_cs = countingSort(comp_median)
while i < len(expenditure) - 1:
	ini = i - d + 1
	if PRINT:
		print(aux_ar_cs)
	med = median(aux_ar_cs, d)
	if med * 2 <= expenditure[i + 1]:
		notifications += 1
	aux_ar_cs[expenditure[i - d + 1]] -= 1
	aux_ar_cs[expenditure[i + 1]] += 1
	i += 1
print(notifications)


class CountingSortArray:

	def __init__(self, max_value):
		self.array = [None for x in range(max_value + 1)]
		self.max_value = max_value
		self.num_elements = 0

	def insert(self, element):
		self.num_elements += 1
		index = element
		array = self.array
		array_element = array[index]
		if array_element is None:
			array_element = {'count': 1, 'value': element}
		else:
			array_element['count'] += 1
		array[index] = array_element

	def remove(self, element):
		self.num_elements -= 1
		index = element
		array = self.array
		array_element = array[index]
		if array_element['count'] == 1:
			array_element = None
		else:
			array_element['count'] -= 1
		array[index] = array_element

	def sorted(self):
		array = self.array
		output = []
		max_value = self.max_value
		for i in range(max_value + 1):
			array_element = array[i]
			if array_element is not None:
				value = array_element['value']
				count = array_element['count']
				for j in range(count):
					output.append(value)
		return output

	def median(self):
		num_elements = self.num_elements
		max_value = self.max_value
		array = self.array
		median = None
		current_index = -1
		if num_elements % 2 != 0:
			expected_index = num_elements // 2
			for i in range(max_value + 1):
				array_element = array[i]
				if array_element is not None:
					value = array_element['value']
					count = array_element['count']
					current_index += count
					if current_index >= expected_index:
						median = value
						break
		else:
			low_index = num_elements // 2 - 1
			high_index = num_elements // 2
			low_element = None
			high_element = None
			for i in range(max_value + 1):
				array_element = array[i]
				if array_element is not None:
					value = array_element['value']
					count = array_element['count']
					current_index += count
					if low_element is None and current_index >= low_index:
						low_element = value
					if high_element is None and current_index >= high_index:
						high_element = value
					if high_element is not None and low_element is not None:
						break
			median = (low_element + high_element) / 2
		return median

def fraudulent_activity_notifications(n, d, expenses):
	last_d_expenses = CountingSortArray(200)
	fraud_notificatons = 0
	for (index, expense) in enumerate(expenses):
		current_day = index + 1
		if current_day > d:
			median = last_d_expenses.median()
			if expense >= 2 * median:
				fraud_notificatons += 1
			to_remove = expenses[index - d]
			last_d_expenses.remove(to_remove)
		last_d_expenses.insert(expense)
	return fraud_notificatons
(n, d) = [int(x) for x in input().strip().split()]
expenses = [int(x) for x in input().strip().split()]
print(fraudulent_activity_notifications(n, d, expenses))


class medtracker(object):

	def __init__(self, a, maxval=200):
		self.counts = [0 for _ in range(maxval + 1)]
		self.max = maxval
		self.n = 0
		for val in a:
			self.n += 1
			self.counts[val] += 1

	@property
	def median(self):
		below = 0
		prev = None
		for ii in range(self.max + 1):
			c = self.counts[ii]
			below += c
			if below >= self.n / 2:
				break
			elif c != 0:
				prev = ii
		if below == self.n / 2:
			for next in range(ii + 1, self.n):
				if self.counts[next] != 0:
					break
			med = (next + ii) / 2
		else:
			med = ii
		return med

	def push(self, new, old):
		self.counts[old] -= 1
		self.counts[new] += 1

	def __repr__(self):
		out = 'Median Tracker - median:{}\n'.format(self.median)
		out += 'Queue: {}'.format(self.q)
		return out
(n, d) = list(map(int, input().split(' ')))
x = list(map(int, input().split(' ')))
t = medtracker(x[:d])
count = 0
for ii in range(d, n):
	if x[ii] >= 2 * t.median:
		count += 1
	t.push(x[ii], x[ii - d])
print(count)


def getMedian(counts, d):
	cum = 0
	if d & 1:
		for i in range(201):
			cum += counts[i]
			if cum > d // 2:
				return i
	else:
		for i in range(201):
			if counts[i] > 0:
				cum += counts[i]
				if cum >= d // 2:
					if cum > d // 2:
						return i
					else:
						j = i + 1
						while a[j] == 0:
							j += 1
						return (i + j) / 2
(n, d) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
counts = [0 for _ in range(200 + 1)]
notices = 0
for i in range(d):
	counts[a[i]] += 1
for i in range(d, n):
	newExp = a[i]
	if newExp >= 2 * getMedian(counts, d):
		notices += 1
	counts[a[i - d]] -= 1
	counts[newExp] += 1
print(notices)


(n, d) = map(int, input().split())
a = list(map(int, input().split()))
w = [0] * 201
for i in range(d):
	w[a[i]] += 1
noti = 0
for i in range(n - d):
	index = li = lo = 0
	if d % 2 != 0:
		for j in range(201):
			index += w[j]
			if index >= d // 2 + 1:
				med = float(j)
				break
	else:
		for j in range(201):
			index += w[j]
			if index >= d // 2 and li == 0:
				li = j
			if index >= d // 2 + 1 and lo == 0:
				lo = j
			if li and lo:
				med = float((li + lo) / 2)
				break
	if a[d + i] >= 2 * med:
		noti += 1
	w[a[i]] -= 1
	w[a[d + i]] += 1
print(noti)


from array import array
from statistics import median
from collections import Counter
from bisect import *

def median(last_d_dict, length):
	md1 = nth_from_dict(last_d_dict, (length + 1) // 2)
	if length % 2 != 0:
		return md1
	else:
		md2 = nth_from_dict(last_d_dict, length // 2 + 1)
		return float(md1 + md2) / 2

def nth_from_dict(last_d_dict, nth):
	idx = 0
	for i in range(200):
		freq = last_d_dict.get(i, 0)
		idx += freq
		if idx >= nth:
			return i

def update(last_d, last_d_dict, entry):
	earliest = last_d.pop(0)
	last_d_dict[earliest] -= 1
	last_d.append(entry)
	last_d_dict[entry] = last_d_dict.get(entry, 0) + 1
(n, d) = input().split()
(n, d) = (int(n), int(d))
nums = array('B', [int(n) for n in input().split()])
fraud = 0
last_d = nums[:d]
last_d_dict = {}
for element in last_d:
	last_d_dict[element] = last_d_dict.get(element, 0) + 1
for i in range(d, n):
	md = median(last_d_dict, len(last_d))
	update(last_d, last_d_dict, nums[i])
	if md * 2 <= nums[i]:
		fraud += 1
print(fraud)


from collections import defaultdict, Counter
(n, d) = [int(x) for x in input().split()]
num = [int(x) for x in input().split()]
first = num[:d]
last = num[d:]
cnt = Counter(first)
ans = 0
for i in range(n - d):
	x = last[i]
	y = num[i]
	med = None
	if d & 1:
		c = 0
		for idx in range(201):
			c += cnt[idx]
			if c >= d // 2 + 1:
				med = idx
				break
	else:
		c = 0
		le = ri = -1
		for idx in range(201):
			c += cnt[idx]
			if c >= d // 2 and le == -1:
				le = idx
			if c >= d // 2 + 1:
				ri = idx
				med = (le + ri) / 2
				break
	if x >= 2 * med:
		ans += 1
	cnt[x] += 1
	cnt[y] -= 1
print(ans)


from math import ceil

def median(C, m, e):
	i = 0
	k = 0
	while i + C[k] < m:
		i += C[k]
		k += 1
	if i + C[k] == m and e:
		med = k
		k += 1
		while C[k] == 0:
			k += 1
		med += k
		return med / 2
	else:
		return k
(n, d) = map(int, input().split())
A = [int(x) for x in input().split()]
C = [0 for i in range(201)]
for i in range(d):
	C[A[i]] += 1
k = d
m = ceil(d / 2)
notif = 0
while k < n:
	med = median(C, m, d % 2 == 0)
	if A[k] >= 2 * med:
		notif += 1
	C[A[k - d]] -= 1
	C[A[k]] += 1
	k += 1
print(notif)


from collections import deque
(m, n) = list(map(int, input().split()))

def fix_up(ar, i, is_min, hdict):
	while i > 0:
		j = (i - 1) // 2
		if is_min:
			if ar[i][0] >= ar[j][0]:
				break
		elif ar[i][0] <= ar[j][0]:
			break
		(ar[i], ar[j]) = (ar[j], ar[i])
		hdict[ar[i]] = i
		hdict[ar[j]] = j
		i = j
	return i

def h_ins(ar, x, is_min, hdict):
	ar.append(x)
	i = len(ar) - 1
	hdict[ar[i]] = i
	fix_up(ar, i, is_min, hdict)

def h_pop(ar, i, is_min, hdict):
	x = ar[i]
	del hdict[ar[i]]
	if len(ar) - 1 == i:
		return ar.pop()
	if i < len(ar):
		ar[i] = ar.pop()
		hdict[ar[i]] = i
		fix_up(ar, i, is_min, hdict)
		while i < len(ar):
			children = [j for j in [2 * i + 1, 2 * i + 2] if j < len(ar)]
			if len(children) == 0:
				break
			k = i
			if is_min:
				for ch in children:
					if ar[ch][0] < ar[k][0]:
						k = ch
			else:
				for ch in children:
					if ar[ch][0] > ar[k][0]:
						k = ch
			if i != k:
				(ar[i], ar[k]) = (ar[k], ar[i])
				hdict[ar[i]] = i
				hdict[ar[k]] = k
				i = k
			else:
				break
	return x

def median(minh, maxh):
	if len(minh) == len(maxh):
		return (minh[0][0] + maxh[0][0]) / 2
	else:
		return minh[0][0]

def smedian(ar):
	ar.sort()
	if len(ar) % 2 == 1:
		return ar[len(ar) // 2]
	else:
		return (ar[len(ar) // 2] + ar[(len(ar) - 1) // 2]) / 2

def update(minh, mind, maxh, maxd, ar, i, j):
	(lmax, lmin) = (len(maxh), len(minh))
	elem_in = (ar[i], i)
	elem_out = (ar[j], j)
	if elem_out in maxd:
		x = h_pop(maxh, maxd[elem_out], False, maxd)
		if x != elem_out:
			print('Error in removing', x, elem_out, maxh, maxd)
	elif elem_out in mind:
		x = h_pop(minh, mind[elem_out], True, mind)
		if x != elem_out:
			print('Error in removing', x, elem_out, minh, mind)
	else:
		print('Invalid element: ', elem_out)
	if len(minh) > 0 and elem_in > minh[0]:
		h_ins(minh, elem_in, True, mind)
	elif len(maxh) > 0 and elem_in <= maxh[0]:
		h_ins(maxh, elem_in, False, maxd)
	else:
		h_ins(minh, elem_in, True, mind)
	if len(minh) > lmin:
		x = h_pop(minh, 0, True, mind)
		h_ins(maxh, x, False, maxd)
	elif len(maxh) > lmax:
		x = h_pop(maxh, 0, False, maxd)
		h_ins(minh, x, True, mind)
ar = list(map(int, input().split()))
notify = 0
ar_n = sorted([(ar[i], i) for i in range(n)])
minh = ar_n[-1 * ((n + 1) // 2):]
mind = {}
for i in range(len(minh)):
	mind[minh[i]] = i
maxh = list(reversed(ar_n[:n // 2]))
maxd = {}
for i in range(len(maxh)):
	maxd[maxh[i]] = i
for i in range(n, len(ar)):
	med = median(minh, maxh)
	if ar[i] >= 2 * med:
		notify += 1
	update(minh, mind, maxh, maxd, ar, i, i - n)
print(notify)


from bisect import bisect_left

class fenwick_tree(object):

	def __init__(self, size=0):
		self.tree = [0] * (size + 1)
		self.size = size

	def push(self, pos):
		pos += 1
		while pos < self.size:
			self.tree[pos] += 1
			pos += pos & -pos

	def pop(self, pos):
		pos += 1
		while pos < self.size:
			self.tree[pos] -= 1
			pos += pos & -pos

	def __getitem__(self, pos):
		res = 0
		while pos > 0:
			res += self.tree[pos]
			pos -= pos & -pos
		return res
(n, d) = map(int, input().split())
csum = fenwick_tree(201)
ar = tuple(map(int, input().split()))
m = d // 2 + 1
if d & 1:

	def twomedian():
		return (bisect_left(csum, m, 1, 201) << 1) - 2
else:
	l = m - 1

	def twomedian():
		a = bisect_left(csum, l, 1, 201)
		return a + bisect_left(csum, m, a, 201) - 2
for i in range(d):
	csum.push(ar[i])
res = 0
for j in range(d, n):
	res += ar[j] >= twomedian()
	csum.push(ar[j])
	csum.pop(ar[j - d])
print(res)


from array import array
from collections import Counter

def median(last_d_dict, length):
	md1 = nth_from_dict(last_d_dict, (length + 1) // 2)
	if length % 2 != 0:
		return md1
	else:
		md2 = nth_from_dict(last_d_dict, length // 2 + 1)
		return float(md1 + md2) / 2

def nth_from_dict(last_d_dict, nth):
	idx = 0
	for i in range(200):
		freq = last_d_dict.get(i, 0)
		idx += freq
		if idx >= nth:
			return i

def update(last_d, last_d_dict, entry):
	earliest = last_d.pop(0)
	last_d_dict[earliest] -= 1
	last_d.append(entry)
	last_d_dict[entry] = last_d_dict.get(entry, 0) + 1
(n, d) = [int(num) for num in input().split()]
nums = array('B', [int(n) for n in input().split()])
fraud = 0
last_d = nums[:d]
last_d_dict = {}
for element in last_d:
	last_d_dict[element] = last_d_dict.get(element, 0) + 1
for i in range(d, n):
	md = median(last_d_dict, len(last_d))
	update(last_d, last_d_dict, nums[i])
	if md * 2 <= nums[i]:
		fraud += 1
print(fraud)


import sys

def readline_ints(stdinp):
	return map(int, stdinp.readline().split())

def calculate_median(expenditures_counter, days):
	middle = days // 2
	count = 0
	if days % 2 == 0:
		median1 = None
		median2 = None
		i = 0
		while i < 201:
			count += expenditures_counter[i]
			if median1 is None and count > middle - 1:
				median1 = i
				if expenditures_counter[i] == 1:
					i += 1
			if median2 is None and count > middle and expenditures_counter[i]:
				median2 = i
				break
			i += 1
		return (median1 + median2) / 2
	for i in range(0, 201):
		count += expenditures_counter[i]
		if count > middle:
			return i

def check_notifications(expenditures, days):
	notifications = 0
	expenditures_counter = [0] * 201
	for day in range(days - 1):
		expenditures_counter[expenditures[day]] += 1
	for day in range(days, len(expenditures)):
		expenditures_counter[expenditures[day - 1]] += 1
		median = calculate_median(expenditures_counter, days)
		expenditures_counter[expenditures[day - days]] -= 1
		if expenditures[day] >= 2 * median:
			notifications += 1
	return notifications

def main(sinp=sys.stdin, sout=sys.stdout):
	(n, days) = readline_ints(sinp)
	sequence = list(readline_ints(sinp))
	print(check_notifications(sequence, days), file=sout)
main()


def counting_sort(arr):
	cnt = [0] * 201
	for i in arr:
		cnt[i] += 1
	return cnt

def median(arr, len_arr):
	mids = []
	if len_arr % 2 == 0:
		v1 = len_arr // 2 - 1
		v2 = len_arr // 2
	else:
		v1 = len_arr // 2
		v2 = None
	run_cnt = -1
	for (i, x) in enumerate(arr):
		run_cnt += x
		if v1 != None:
			if v1 <= run_cnt:
				v1 = None
				mids.append(i)
		if v2 != None:
			if v2 <= run_cnt:
				v2 = None
				mids.append(i)
		if v1 == None and v2 == None:
			return sum(mids) / len(mids)

def alert(m, s):
	if s >= 2 * m:
		return True
	else:
		return False
(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
count = counting_sort(arr[:d])
alert_cnt = 0
for day in range(d, n):
	m = median(count, d)
	if alert(m, arr[day]):
		alert_cnt += 1
	count[arr[day - d]] -= 1
	count[arr[day]] += 1
print(alert_cnt)


(n, d) = [int(_) for _ in input().strip().split()]
arr = [int(_) for _ in input().strip().split()]
SIZE = 8

def tree_insert(tree, x):
	for i in range(SIZE):
		tree[i][x] += 1
		x >>= 1

def tree_erase(tree, x):
	for i in range(SIZE):
		tree[i][x] -= 1
		x >>= 1

def kth_element(tree, k):
	a = 0
	b = SIZE - 1
	while b >= 0:
		a *= 2
		if tree[b][a] <= k:
			k -= tree[b][a]
			a += 1
		b -= 1
	return a

def median(tree, d):
	p = d // 2
	if d & 1:
		return kth_element(tree, p)
	else:
		return (kth_element(tree, p - 1) + kth_element(tree, p)) / 2
tree = [[0] * 2 ** (SIZE - i) for i in range(SIZE)]
notifications = 0
for i in range(d):
	tree_insert(tree, arr[i])
for i in range(d, n):
	m = median(tree, d)
	if arr[i] >= 2 * m:
		notifications += 1
	tree_insert(tree, arr[i])
	tree_erase(tree, arr[i - d])
print(notifications)


def calc_median(hist, n):
	wsum = 0
	central = n // 2
	if n % 2:
		for i in range(len(hist)):
			wsum += hist[i]
			if wsum > central:
				return float(i)
	else:
		left = -1
		right = -1
		for i in range(len(hist)):
			wsum += hist[i]
			if wsum >= central and left == -1:
				left = i
			if wsum > central and right == -1:
				right = i
			if left > -1 and right > -1:
				if left + right == 0:
					return 0
				else:
					return float(left + right) / 2
(n, d) = [int(x) for x in input().split(' ')]
exp = [int(x) for x in input().split(' ')]
hist = [0] * 201
notifications = 0
for i in range(d):
	hist[exp[i]] += 1
for i in range(n - d):
	median = calc_median(hist, d)
	if exp[i + d] >= median * 2:
		notifications += 1
	hist[exp[i + d]] += 1
	hist[exp[i]] -= 1
print(notifications)


import sys

def getmid(cn, nmid, sumBelow):
	global d, mid, mid1
	if sumBelow >= mid:
		k = nmid
		ssum = sumBelow
		while ssum >= mid:
			k -= 1
			ssum -= cn[k]
		nmid = k
		sumBelow = ssum
		ssum = sumBelow + cn[k]
	else:
		k = nmid - 1
		ssum = sumBelow
		while ssum < mid:
			k += 1
			ssum += cn[k]
		nmid = k
		sumBelow = ssum - cn[k]
	if mid == mid1:
		return (nmid, nmid, sumBelow)
	if ssum >= mid1:
		nmid1 = k
	else:
		while ssum < mid1:
			k += 1
			ssum += cn[k]
		nmid1 = k
	return (nmid, nmid1, sumBelow)

def main():
	ins = [int(value) for value in input().strip().split()]
	n = ins[0]
	global d, mid, mid1
	d = ins[1]
	mid = int((d + 1) / 2)
	even = True if d % 2 == 0 else False
	mid1 = mid + 1 if even else mid
	q = [int(q_temp) for q_temp in input().strip().split(' ')]
	mmax = 200
	cn = [0 for i in range(mmax + 1)]
	for i in range(d):
		cn[q[i]] += 1
	(nmid, nmid1, sumBelow) = getmid(cn, 0, 0)
	ncount = 0
	for i in range(d, n):
		median2 = nmid + nmid1
		if q[i] >= median2:
			ncount += 1
		idd = i - d
		cn[q[idd]] -= 1
		cn[q[i]] += 1
		if q[idd] < nmid:
			sumBelow -= 1
		if q[i] < nmid:
			sumBelow += 1
		if q[idd] < nmid and q[i] < nmid:
			pass
		elif q[idd] > nmid1 and q[i] > nmid1:
			pass
		else:
			(nmid, nmid1, sumBelow) = getmid(cn, nmid, sumBelow)
	print(ncount)
main()


__author__ = 'sidwagz'
import bisect

def median(arr):
	if len(arr) & 1:
		return arr[len(arr) // 2]
	else:
		return sum(arr[len(arr) // 2 - 1:len(arr) // 2 + 1]) / 2.0
(l, d) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
nots = 0
last = sorted(arr[-d:])
for l in range(l - d - 1, -1, -1):
	r = l + d
	temp = bisect.bisect(last, arr[r])
	last.pop(temp - 1)
	bisect.insort(last, arr[l])
	cutoff = 2 * median(last)
	if arr[r] >= cutoff:
		nots += 1
print(nots)


import bisect

def index(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	raise ValueError
tt = set()

def banking(arr, n, d):
	window = []
	head_idx = 0
	notifications = 0
	for (day, day_cost) in enumerate(arr):
		if day < d:
			bisect.insort(window, day_cost)
			continue
		median = -1
		if d % 2 == 0:
			median = (window[d // 2] + window[d // 2 - 1]) / 2
		else:
			median = window[d // 2]
		if day_cost >= 2 * median:
			notifications += 1
		tt.add(2 * median)
		start_idx = index(window, arr[head_idx])
		del window[start_idx]
		bisect.insort(window, day_cost)
		head_idx += 1
	return notifications

def main():
	(n, d) = [int(x) for x in input().strip().split()]
	arr = [int(x) for x in input().strip().split()]
	print(banking(arr, n, d))
main()


(n, d) = [int(i) for i in input().strip().split()]
arr = [int(i) for i in input().strip().split()]
import collections

class queue(collections.deque):

	def pop(self):
		return self.popleft()

	def push(self, n):
		self.append(n)
counts = [0 for i in range(201)]
last = queue()
for i in range(d):
	counts[arr[i]] += 1
	last.push(arr[i])
median_i = (d - 1) // 2

def median(counts, d):
	odd = d % 2 == 1
	i = -1
	k = -1
	while k < median_i:
		i += 1
		k += counts[i]
	if odd:
		return i
	elif k > median_i:
		return i
	else:
		a = i
		i += 1
		while counts[i] == 0:
			i += 1
		b = i
		return (a + b) / 2.0
notifications = 0
for i in range(d, n):
	n = arr[i]
	m = median(counts, d)
	if n >= 2 * m:
		notifications += 1
	if len(last) > 0:
		l = last.pop()
		counts[l] -= 1
	counts[n] += 1
	last.push(n)
print(notifications)


from bisect import insort, bisect_left

def partition(array, left, right):
	pivot = array[right]
	i = left - 1
	for j in range(left, right):
		if array[j] < pivot:
			i += 1
			(array[i], array[j]) = (array[j], array[i])
	(array[i + 1], array[right]) = (array[right], array[i + 1])
	return (array, i + 1)

def quicksort(l, left, right):
	if left < right:
		(l, pivot) = partition(l, left, right)
		quicksort(l, left, pivot - 1)
		quicksort(l, pivot + 1, right)
	return l

def get_median(array):
	n = len(array)
	if n % 2 == 0:
		n_ = n // 2 - 1
		return sum(array[n_:n_ + 2]) / 2
	else:
		return array[int(n / 2)]
(n, d) = [int(i.strip()) for i in input().split()]
ar = [int(i) for i in input().strip().split()]
notifications = 0
exp = quicksort(ar[:d].copy(), 0, d - 1)
m = get_median(exp)
for today in range(d, n):
	if ar[today] >= 2 * m:
		notifications += 1
	del exp[bisect_left(exp, ar[today - d])]
	insort(exp, ar[today])
	m = get_median(exp)
print(notifications)


import bisect
import itertools
(n, d) = list(map(int, input().split()))
a = input().split()
count = 0
x = 0
to_remove = [int(i) for i in a[:d]]
window = sorted(to_remove)
even = d % 2 == 0
if even:
	mid1 = int(d / 2 - 1)
	mid2 = int(d / 2)
else:
	mid = int(d / 2)
if even:
	for i in range(d, n):
		x = int(a[i])
		if x >= window[mid1] + window[mid2]:
			count += 1
		del window[bisect.bisect_left(window, to_remove.pop(0))]
		bisect.insort(window, x)
		to_remove.append(x)
else:
	for i in range(d, n):
		x = int(a[i])
		if x >= 2 * window[mid]:
			count += 1
		del window[bisect.bisect_left(window, to_remove.pop(0))]
		bisect.insort(window, x)
		to_remove.append(x)
print(count)


from collections import deque
EXPENDITURES = 200

def get_the_median(record, d):
	d2 = d // 2
	for i in range(EXPENDITURES + 1):
		if record[i][1] is not None and d2 <= record[i][1]:
			m1 = i
			if d % 2 == 0:
				if d2 - 1 >= record[i][0]:
					m2 = i
				else:
					for j in range(i - 1, -1, -1):
						if record[j][0] is not None:
							m2 = j
							break
			break
	if d % 2 == 1:
		return m1
	else:
		return (m1 + m2) / 2

def update(added, last_d_days, record, d):
	last_d_days.append(added)
	dropped = last_d_days.popleft()
	if added > dropped:
		delta = 1
	elif added < dropped:
		delta = -1
	else:
		delta = 0
	if delta == 1:
		if record[dropped][1] > record[dropped][0]:
			record[dropped][1] -= 1
			last = record[dropped][1]
		else:
			last = record[dropped][1] - 1
			record[dropped] = [None, None]
		for i in range(dropped + 1, added, delta):
			try:
				if record[i][0] > 0:
					record[i][0] -= 1
					record[i][1] -= 1
					last = record[i][1]
			except TypeError:
				pass
		try:
			if record[added][0] > 0:
				record[added][0] -= 1
		except TypeError:
			record[added][0] = record[added][1] = last + 1
	elif delta == -1:
		if record[dropped][1] > record[dropped][0]:
			record[dropped][0] += 1
			last = record[dropped][0]
		else:
			last = record[dropped][0] + 1
			record[dropped] = [None, None]
		for i in range(dropped + delta, added, delta):
			if record[i][0] is not None:
				record[i][1] += 1
				record[i][0] += 1
				last = record[i][0]
		if record[added][1] is not None:
			record[added][1] += 1
		else:
			record[added][0] = record[added][1] = last - 1
		return

def main():
	(n, d) = map(int, input().strip().split())
	spending = tuple(map(int, input().strip().split()))
	notifications = 0
	last_d_days = deque(spending[:d])
	ds = sorted(last_d_days)
	expenditure_limit = 200
	ds_record = [[None, None] for _i in range(expenditure_limit + 1)]
	for ind in range(d):
		if ds_record[ds[ind]][1] is not None:
			ds_record[ds[ind]][1] += 1
		else:
			ds_record[ds[ind]] = [ind, ind]
	median = get_the_median(ds_record, d)
	if spending[d] >= 2 * median:
		notifications += 1
	zeros = []
	for i in range(n):
		if spending[i] == 0:
			zeros.append(i)
	for i in range(d + 1, n):
		update(spending[i - 1], last_d_days, ds_record, d)
		median = get_the_median(ds_record, d)
		if spending[i] >= 2 * median:
			notifications += 1
	print(notifications)
main()


import sys
from bisect import insort, bisect_left
from itertools import islice

def limit(s, even, mid):
	return s[mid] + (even and s[mid - 1] or s[mid])

def count_notifications(n, d, exp):
	s = []
	s_pop = s.pop
	for v in islice(exp, d):
		insort(s, v)
	notifications = 0
	mid = d // 2
	even = d % 2 == 0
	for i in range(d, n):
		v = exp[i]
		if v >= limit(s, even, mid):
			notifications += 1
		p = bisect_left(s, exp[i - d])
		s_pop(p)
		insort(s, v)
	return notifications
(n, d) = map(int, input().split())
exp = list(map(int, input().split()))
number_of_notifications = count_notifications(n, d, exp)
print(number_of_notifications)


(n, d) = list(map(int, input().strip().split(' ')))
a = list(map(int, input().strip().split(' ')))
MAX_SIZE = 200
occurences = [0] * (MAX_SIZE + 1)
occurences[a[0]] = 1
onLeft = 0
currentMedian = a[0]
onRight = 0

def giveLeft(occurences, currentMedian):
	currentMedian -= 1
	while occurences[currentMedian] == 0:
		currentMedian -= 1
	return currentMedian

def giveRight(occurences, currentMedian):
	currentMedian += 1
	while occurences[currentMedian] == 0:
		currentMedian += 1
	return currentMedian
count = 0
for i in range(1, n):
	v = a[i]
	if i >= d:
		val = currentMedian * 2
		if d % 2 == 0:
			otherMedian = currentMedian
			if onLeft + occurences[currentMedian] == onRight:
				otherMedian = giveRight(occurences, currentMedian)
			val = otherMedian + currentMedian
		if v >= val:
			count += 1
	occurences[v] += 1
	if v > currentMedian:
		onRight += 1
	elif v < currentMedian:
		onLeft += 1
	if i >= d:
		removedV = a[i - d]
		occurences[removedV] -= 1
		if removedV > currentMedian:
			onRight -= 1
		elif removedV < currentMedian:
			onLeft -= 1
	while onRight + occurences[currentMedian] <= onLeft:
		onRight += occurences[currentMedian]
		currentMedian = giveLeft(occurences, currentMedian)
		onLeft -= occurences[currentMedian]
	while onLeft + occurences[currentMedian] < onRight:
		onLeft += occurences[currentMedian]
		currentMedian = giveRight(occurences, currentMedian)
		onRight -= occurences[currentMedian]
print(count)


import bisect
import statistics
from heapq import heappush, heappop

def parse(s):
	return [int(p) for p in s.split()]

def main():
	(ntrans, days) = parse(input())
	trans = parse(input())
	b = [0] * 201
	for x in trans[:days]:
		b[x] += 1
	j = days
	counter = 0
	while j < ntrans:
		(acc, q) = (0, 0)
		for (i, v) in enumerate(b):
			acc += v
			t = days // 2 + 1
			if acc >= t:
				if days & 1 == 1 or acc - v != t - 1:
					q = i
				else:
					q = (i + q) / 2
				break
			q = i
		if trans[j] >= 2 * q:
			counter += 1
		b[trans[j]] += 1
		b[trans[j - days]] -= 1
		j += 1
	print(counter)
main()


def counting_sort(ar: list) -> list:
	LIST = [0] * 201
	for a in ar:
		LIST[a] += 1
	return LIST

def median(l: list, ds: int) -> int:
	m = ds // 2 + 1
	temp = 0
	last = 0
	while l[last] == 0:
		last += 1
	if m == 1:
		return last
	for (i, a) in enumerate(l):
		temp += a
		if temp == m:
			if a > 1:
				return i
			elif a == 1:
				if ds % 2 == 1:
					return i
				else:
					return (last + i) / 2
			else:
				return last
		elif temp > m:
			if ds % 2 == 1:
				return i
			elif a == temp - m + 1:
				return (last + i) / 2
			else:
				return i
		if a != 0:
			last = i

def notifications(total: int, days: int, ex: list) -> int:
	if days == total:
		return 0
	counts = 0
	current = counting_sort(ex[:days])
	med = median(current, days)
	index = days
	while index < len(ex):
		if index > days:
			current[ex[index - days - 1]] -= 1
			current[ex[index - 1]] += 1
			med = median(current, days)
		if ex[index] >= 2 * med:
			counts += 1
		index += 1
	return counts
(n, d) = (int(x) for x in input().strip().split(' '))
exps = [int(x) for x in input().strip().split(' ')]
print(notifications(n, d, exps))


import bisect as bi
import math as m
(n, d) = map(int, input().split())
arr = list(map(int, input().split()))
hasht = [0] * 201
for i in range(d):
	hasht[arr[i]] += 1
mid = int(m.ceil(d / 2))
med = 0
flag = 0
cnt = 0
for i in range(0, n - d):
	if d % 2:
		ctr = 0
		for j in range(201):
			ctr += hasht[j]
			if ctr >= mid:
				break
		med = j
	else:
		ctr = 0
		st = -1
		en = -1
		for j in range(201):
			ctr += hasht[j]
			if ctr == mid:
				st = j
			if ctr > mid:
				en = j
				break
		if st + 1 == 0:
			st = en
		med = (st + en) / 2
	if med * 2 <= arr[i + d]:
		cnt += 1
	hasht[arr[i + d]] += 1
	hasht[arr[i]] -= 1
print(cnt)


import bisect
(n, d) = (int(i) for i in input().split(' '))
arr = [int(i) for i in input().split(' ')]
res = 0
median = 0
start = 0
finish = d
l = []
for i in range(0, d):
	bisect.insort(l, arr[i])
	k = bisect.bisect(l, arr[i])
for i in range(d, len(arr)):
	if d % 2 == 0:
		median = (l[d // 2] + l[d // 2 - 1]) / 2
	else:
		median = l[d // 2]
	if arr[i] >= 2 * median:
		res += 1
	del l[bisect.bisect(l, arr[i - d]) - 1]
	bisect.insort(l, arr[i])
print(res)


import bisect
(_, days) = (int(num_str) for num_str in input().strip().split(' '))
amounts = [int(num_str) for num_str in input().strip().split(' ')]
sorted_amounts = sorted(amounts[:days])
sorted_amounts = sorted(amounts[:days])

def get_double_median(nums):
	odd = len(nums) % 2 == 1
	if odd:
		median = nums[len(nums) // 2]
	else:
		middle = len(nums) // 2
		median = (nums[middle - 1] + nums[middle]) / 2
	return int(median * 2)
notifications = 0
for day in range(days, len(amounts)):
	amount = amounts[day]
	double_median = get_double_median(sorted_amounts)
	if amount >= double_median:
		notifications += 1
	bisect.insort(sorted_amounts, amount)
	to_remove_value = amounts[day - days]
	to_remove_index = bisect.bisect_left(sorted_amounts, to_remove_value)
	del sorted_amounts[to_remove_index]
print(notifications)


from collections import Counter
(n, d) = input().split()
(n, d) = (int(n), int(d))
trans = list(map(int, input().split()))
alerts = 0
window = Counter(trans[:d])

def counting_med(window):
	total = 0
	for i in range(201):
		total += window[i]
		if d % 2 == 0 and total == d // 2:
			return i + 0.5
		elif total > d // 2:
			return i
for i in range(d, n):
	median = counting_med(window)
	this_trans = trans[i]
	if this_trans >= 2 * median:
		alerts += 1
	window[trans[i - d]] -= 1
	window[trans[i]] += 1
print(alerts)


from bisect import bisect_right, bisect_left
(n, d) = map(int, input().split())
exp = list(map(int, input().split()))
if d >= n:
	print(0)
	exit()
ans = 0
a = sorted(exp[0:d])
for i in range(d, n):
	if d % 2 != 0:
		median = a[d // 2]
	else:
		median = (a[d // 2] + a[d // 2 - 1]) / 2
	if exp[i] >= 2 * median:
		ans += 1
	a.pop(bisect_left(a, exp[i - d]))
	ind = bisect_right(a, exp[i])
	a.insert(ind, exp[i])
print(ans)


def medi(ar):
	if dr == 0:
		return 0.5 * (ar[dm] + ar[dm - 1])
	else:
		return ar[dm]

def bs(array, target):
	lower = 0
	upper = len(array)
	while lower < upper:
		x = lower + (upper - lower) // 2
		val = array[x]
		if target == val:
			return x
		elif target > val:
			if lower == x:
				return upper
			lower = x
		elif target < val:
			upper = x
	return lower

def medr(ar, a1, a2):
	x1 = bs(ar, a1)
	del ar[x1]
	x1 = bs(ar, a2)
	ar[x1:x1] = [a2]
	return ar
(n, d) = [int(c) for c in input().strip().split()]
txns = [int(c) for c in input().strip().split()]
dr = d % 2
dm = d // 2
noti = 0
for j in range(n - d):
	curr = txns[j + d]
	if j < 1:
		a = list(txns[j:j + d])
		a = sorted(a)
	else:
		a = medr(a, txns[j - 1], txns[j + d - 1])
	med = medi(a)
	if 2 * med <= curr:
		noti += 1
print(noti)


def readInts():
	return map(int, input().strip().split())

def fraudulent_activity_notifications():

	def x2median_array(e):
		lo_count = 0
		lo_value = -1
		lo_value_data = None
		hi_count = 0
		hi_value = 201
		hi_value_data = None
		while lo_value < hi_value - 1:
			if lo_count > hi_count:
				hi_value -= 1
				v = e[hi_value]
				if v > 0:
					hi_value_data = hi_value
				hi_count += v
			else:
				lo_value += 1
				v = e[lo_value]
				if v > 0:
					lo_value_data = lo_value
				lo_count += e[lo_value]
		if lo_count > hi_count:
			return lo_value_data * 2
		elif lo_count < hi_count:
			return hi_value_data * 2
		else:
			return lo_value_data + hi_value_data
	(n, d) = readInts()
	expenditures = list(readInts())
	values = [0 for _ in range(201)]
	out = 0
	en = len(expenditures)
	for i in range(en):
		e = expenditures[i]
		if i >= d:
			e_minus_d = expenditures[i - d]
			x2med = x2median_array(values)
			if e >= x2med:
				out += 1
			values[e_minus_d] -= 1
		values[e] += 1
	print(out)
fraudulent_activity_notifications()


import sys
import statistics
found_remove = -1

def binary_remove(array, start, end, remove_num):
	global found_remove
	if start == end:
		return
	middle = int((start + end) / 2)
	if remove_num < array[middle]:
		binary_remove(array, start, middle, remove_num)
	elif remove_num > array[middle]:
		binary_remove(array, middle, end, remove_num)
	else:
		found_remove = middle
found_insert = -1

def binary_insert(array, start, end, insert_num):
	global found_insert
	if start == end:
		return
	if start + 1 == end:
		if array[start] < insert_num:
			found_insert = start + 1
		else:
			found_insert = start
		return
	middle = int((start + end) / 2)
	if array[middle] < insert_num:
		binary_insert(array, middle, end, insert_num)
	elif array[middle] >= insert_num:
		binary_insert(array, start, middle, insert_num)

def parse_input(line):
	l = line.split('\n')
	l1split = l[0].split(' ')
	n = eval(l1split[0])
	d = eval(l1split[1])
	l2split = l[1].split(' ')
	days = []
	for i in l2split:
		days.append(eval(i))
	return (n, d, days)

def run_through(n, d, days):
	global found_remove
	global found_insert
	count = 0
	initial = days[:d]
	initial.sort()
	median = statistics.median(initial)
	if days[d] >= median * 2:
		count += 1
	for end in range(d + 1, n - 1):
		to_remove = days[end - d - 1]
		today = days[end]
		yesterday = days[end - 1]
		found_remove = -1
		binary_remove(initial, 0, len(initial), to_remove)
		del initial[found_remove]
		found_insert = -1
		binary_insert(initial, 0, len(initial), yesterday)
		initial.insert(found_insert, yesterday)
		if len(initial) != d:
			print('WTF!')
		if len(initial) % 2 == 1:
			m = int(len(initial) / 2)
			median = initial[m]
		else:
			m2 = int(len(initial) / 2)
			m1 = int(len(initial) / 2) - 1
			median = (initial[m1] + initial[m2]) / 2
		if days[end] >= median * 2:
			count += 1
	return count
line = sys.stdin.read()
(n, d, days) = parse_input(line)
answer = run_through(n, d, days)
print(answer)


import bisect

def median(arr):
	s = sorted(arr)
	length = len(arr)
	if length % 2 != 0:
		return s[length // 2]
	else:
		return (s[length // 2] + s[length // 2 - 1]) / 2

def update_list(l, to_remove, to_add):
	idx = bisect.bisect_left(l, to_remove)
	del l[idx]
	idx2 = bisect.bisect(l, to_add)
	l.insert(idx2, to_add)

def median_from_sorted(arr):
	length = len(arr)
	if length % 2 != 0:
		return arr[length // 2]
	else:
		return (arr[length // 2] + arr[length // 2 - 1]) / 2

def count_notifications(arr, d):
	result = 0
	length = len(arr)
	sorted_transactions = sorted(arr[0:d])
	for i in range(d, length):
		m = median_from_sorted(sorted_transactions)
		if arr[i] >= 2 * m:
			result += 1
		update_list(sorted_transactions, arr[i - d], arr[i])
	return result
(_, d) = [int(i) for i in input().strip().split()]
arr = [int(i) for i in input().strip().split()]
print(count_notifications(arr, d))


def median_counter(arr, d):
	k = d // 2
	counter = 0
	if d % 2:
		for (idx, val) in zip(range(201), arr):
			counter += val
			if counter > k:
				return idx
	else:
		flag = False
		lo = 0
		for (idx, val) in zip(range(201), arr):
			counter += val
			if counter == k and (not flag):
				(flag, lo) = (True, idx)
			if flag and counter > k:
				return 0.5 * (lo + idx)
			if counter > k:
				return idx
(n, d) = [int(val) for val in input().split()]
counts = [0] * 201
arr = [int(val) for val in input().split()]
if d == n:
	print(0)
else:
	for val in arr[:d]:
		counts[val] += 1
	notifs = 0
	for (old, val) in zip(arr[:-d], arr[d:]):
		median = median_counter(counts, d)
		if val >= 2 * median:
			notifs += 1
		counts[val] += 1
		counts[old] -= 1
	print(notifs)


from bisect import insort
from bisect import bisect_left
from statistics import median
(N, d) = [int(x) for x in input().split(' ')]
Days = [int(x) for x in input().split(' ')]
Notifications = 0
newList1 = Days[0:d]
newList2 = sorted(newList1)
med = median(newList1)
index = d // 2
for i in range(d, N):
	if Days[i] >= 2 * med:
		Notifications += 1
	del newList2[bisect_left(newList2, Days[i - d])]
	insort(newList2, Days[i])
	if d % 2 == 0:
		med = (newList2[d // 2 - 1] + newList2[d // 2]) / 2
	else:
		med = newList2[d // 2]
print(Notifications)


import sys
(n, d) = [int(arr_temp) for arr_temp in input().strip().split(' ')]
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]

def medianFromSorted(arr):
	n_tmp = len(arr)
	if n_tmp % 2 == 1:
		return arr[(n_tmp - 1) // 2]
	else:
		return 0.5 * (arr[n_tmp // 2 - 1] + arr[n_tmp // 2])

def addToSortedList(arr, x):
	n_tmp = len(arr)
	i = 0
	j = n_tmp - 1
	while j - i > 1:
		k = int(0.5 * (i + j))
		if x > arr[k]:
			i = k
		elif x < arr[k]:
			j = k
		else:
			arr.insert(k, x)
			return
	if x <= arr[i]:
		arr.insert(i, x)
	elif x >= arr[j]:
		arr.insert(j + 1, x)
	else:
		arr.insert(i + 1, x)

def removeFromSortedList(arr, x):
	n_tmp = len(arr)
	i = 0
	j = n_tmp - 1
	while j != i:
		k = int(0.5 * (i + j))
		if x > arr[k]:
			i = k
		elif x < arr[k]:
			j = k
		else:
			del arr[k]
			return

def generateArrMedian(arr, n, d):
	arr_median = [0] * n
	tmp = list(arr[0:d])
	tmp.sort()
	arr_median[d] = medianFromSorted(tmp)
	for i in range(d + 1, n):
		removeFromSortedList(tmp, arr[i - 1 - d])
		addToSortedList(tmp, arr[i - 1])
		arr_median[i] = medianFromSorted(tmp)
	return arr_median

def countBreaches(arr, n, d):
	counter = 0
	arr_median = generateArrMedian(arr, n, d)
	for i in range(d, n):
		if arr[i] >= 2 * arr_median[i]:
			counter += 1
	return counter
print(countBreaches(arr, n, d))


(n, d) = [int(x) for x in input().split()]
data = [int(d) for d in input().split()]
count = [0] * 201
for i in range(d):
	count[data[i]] += 1
hits = 0
for i in range(d, n):
	if d % 2 == 1:
		finder = d // 2
		found = 0
		ind = -1
		while found <= finder:
			ind += 1
			found += count[ind]
		med2 = ind * 2
	else:
		finder = d // 2
		found = 0
		ind = -1
		while found < finder:
			ind += 1
			found += count[ind]
		ind1 = ind
		while found <= finder:
			ind += 1
			found += count[ind]
		ind2 = ind
		med2 = ind1 + ind2
	if data[i] >= med2:
		hits += 1
	count[data[i]] += 1
	count[data[i - d]] -= 1
print(hits)


import sys
from math import floor

def slide_window(win, rm, ins):
	if rm != ins:
		remove_from_window(win, 0, len(win) - 1, rm)
		insert_into_window(win, 0, len(win) - 1, ins)

def insert_into_window(win, sIdx, eIdx, elem):
	if elem < win[sIdx]:
		win.insert(0, elem)
	elif elem > win[eIdx]:
		win.append(elem)
	else:
		inserted = False
		while not inserted and sIdx < eIdx:
			mid = sIdx + int((eIdx - sIdx) / 2)
			if win[mid] > elem:
				eIdx = mid - 1
			elif win[mid] < elem:
				sIdx = mid + 1
			else:
				win.insert(mid, elem)
				inserted = True
		if not inserted:
			win.insert(sIdx if elem < win[sIdx] else sIdx + 1, elem)

def remove_from_window(win, sIdx, eIdx, elem):
	while sIdx <= eIdx:
		mid = sIdx + int((eIdx - sIdx) / 2)
		if win[mid] > elem:
			eIdx = mid - 1
		elif win[mid] < elem:
			sIdx = mid + 1
		else:
			del win[mid]
			break

def median(items, l):
	if l % 2 == 0:
		return (items[int(l / 2)] + items[int(l / 2) - 1]) / 2
	else:
		return items[floor(l / 2)]
(n, d) = [int(tmp) for tmp in input().strip().split(' ')]
days = [int(tmp) for tmp in input().strip().split(' ')]
win = sorted(days[0:d])
i = d
alert_ct = 0
while i < n:
	amt = days[i]
	if amt >= median(win, d) * 2:
		alert_ct += 1
	slide_window(win, days[i - d], amt)
	i += 1
print(alert_ct)


class Account:

	def __init__(self, num_of_days):
		self.d_queue = []
		self.d_dict = dict()
		self.median = None
		self.d = num_of_days
		self.count = 0
		self.alarm_account = 0

	def push(self, value):
		if self.median and value >= self.median * 2:
			self.alarm_account += 1
		if self.count == self.d:
			removed = self.d_queue.pop(0)
			self.d_dict[removed] -= 1
			if self.d_dict[removed] == 0:
				self.d_dict.pop(removed, None)
		else:
			self.count += 1
		self.d_queue.append(value)
		if value in self.d_dict:
			self.d_dict[value] += 1
		else:
			self.d_dict[value] = 1
		if self.count < self.d:
			return
		sum = 0
		even_number = 1 if self.count % 2 == 0 else 0
		target = int((self.count + 1) / 2) if not even_number else int(self.count / 2)
		for value in sorted(self.d_dict):
			sum += self.d_dict[value]
			if sum >= target:
				if not even_number:
					self.median = value
				elif sum > target:
					self.median = value
				else:
					next_value = value + 1
					while next_value not in self.d_dict:
						next_value += 1
					self.median = (value + next_value) / 2
				break
(n, d) = [int(value) for value in input().strip().split(' ')]
my_account = Account(d)
array = [int(value) for value in input().strip().split(' ')]
for value in array:
	my_account.push(value)
print(my_account.alarm_account)


(n, d) = map(int, input().split())
hd = d / 2
data = list(map(int, input().split()))
count = 201 * [0]
for i in range(d):
	count[data[i]] += 1

def i_at_pos(count, pos):
	i = -1
	s = 0
	for e in count:
		i += 1
		if e:
			s += e
			if s > pos:
				break
	return i

def median2(count, n):
	odd = n % 2 == 1
	if odd:
		return i_at_pos(count, n // 2)
	else:
		return 0.5 * (i_at_pos(count, n // 2 - 1) + i_at_pos(count, n // 2))
res = 0
for j in range(d, n):
	if data[j] >= 2 * median2(count, d):
		res += 1
	count[data[j]] += 1
	count[data[j - d]] -= 1
print(res)


def count_repetitions(first_period):
	counted = [0] * 201
	for i in range(len(first_period)):
		counted[first_period[i]] += 1
	return counted

def compute_median(helper, p):
	index = 0
	if p % 2 == 0:
		(next, prev) = (0, 0)
		for i in range(201):
			index += helper[i]
			if index >= p // 2 and prev == 0:
				prev = i
			if index >= p // 2 + 1 and next == 0:
				next = i
				break
		median = (prev + next) / 2
	else:
		for i in range(201):
			index += helper[i]
			if index >= p // 2 + 1:
				median = i
				break
	return median

def need_notify(current, median):
	if current >= 2 * median:
		return True
	else:
		return False

def compute_notifications_v2(trs, period):
	notifications = 0
	helper = count_repetitions(trs[:period])
	for i in range(period, len(trs)):
		median = compute_median(helper, period)
		if need_notify(trs[i], median):
			notifications += 1
		helper[trs[i - period]] -= 1
		helper[trs[i]] += 1
	return notifications

def compute_notifications(trs, period):
	if period >= len(trs):
		return 0
	notifications = 0
	if period % 2:
		median_odd = True
		median_pos = period // 2
	else:
		median_odd = False
		median_pos = period // 2 - 1
	sorted_p = trs[:period]
	for i in range(period, len(trs)):
		if median_odd:
			median = find_kth(sorted_p, len(sorted_p), median_pos)
		else:
			median = (find_kth(sorted_p, len(sorted_p), median_pos) + find_kth(sorted_p, len(sorted_p), median_pos + 1)) / 2
		if trs[i] >= 2 * median:
			notifications += 1
		sorted_p = sorted_p[1:]
		sorted_p.append(trs[i])
	return notifications
(n, d) = map(int, input().split())
transactions = [int(elem) for elem in input().split()]
print(compute_notifications_v2(transactions, d))


class MedianCalculator:

	def __init__(self):
		self.size = 200 + 1
		self.n = 0
		self.lst = [0] * self.size

	def add(self, num):
		self.lst[num] += 1
		self.n += 1

	def remove(self, num):
		self.lst[num] -= 1
		self.n -= 1

	def median(self):
		n = self.n
		lst = self.lst
		half_n = n // 2
		prev_half_n = half_n - 1
		index = -1
		(first, second) = (-1, -1)
		for i in range(self.size):
			if lst[i] != 0:
				if second == -1 and index + lst[i] >= prev_half_n:
					second = i
				if index + lst[i] >= half_n:
					first = i
					break
				index += lst[i]
		return first if n % 2 != 0 else (first + second) / 2

def check(lst, mc, i, num):
	ret = 0
	median = mc.median()
	if num >= 2 * median:
		ret = 1
	d = len(lst)
	mc.remove(lst[i % d])
	lst[i % d] = num
	mc.add(lst[i % d])
	return ret

def notification(lst, nums):
	mc = MedianCalculator()
	for num in lst:
		mc.add(num)
	return sum([check(lst, mc, i, num) for (i, num) in enumerate(nums)])

def main():
	(n, d) = [int(x) for x in input().split()]
	nums = (int(x) for x in input().split())
	lst = [next(nums) for _ in range(d)]
	print(notification(lst, nums))
main()


def calculate_median(counts, d):
	cumulative_count = 0
	for (expenditure, count) in enumerate(counts):
		cumulative_count += count
		if cumulative_count > (d + 1) // 2:
			return expenditure
		elif cumulative_count == (d + 1) // 2:
			if d % 2 == 1:
				return expenditure
			else:
				next_expenditure = expenditure + 1
				while not counts[next_expenditure]:
					next_expenditure += 1
				return (expenditure + next_expenditure) / 2
(n, d) = map(int, input().split())
counts = [0] * 201
expenditures = [int(s) for s in input().split()]
for i in range(d):
	counts[expenditures[i]] += 1
notification_count = 0
for i in range(d, n):
	if expenditures[i] >= 2 * calculate_median(counts, d):
		notification_count += 1
	counts[expenditures[i - d]] -= 1
	counts[expenditures[i]] += 1
print(notification_count)


import sys
(n, d) = [int(s) for s in input().strip().split(' ')]
ints = [int(s) for s in input().strip().split(' ')]

class SortedList:

	def __init__(self):
		self.data = []

	def insert(self, value):
		(l, r) = (0, len(self.data))
		while r - l > 0:
			m = l + (r - l) // 2
			if value == self.data[m]:
				l = r = m
				continue
			if value < self.data[m]:
				r = m
				continue
			l = m + 1
		self.data.insert(l, value)

	def remove(self, value):
		(l, r) = (0, len(self.data))
		while r - l > 0:
			m = l + (r - l) // 2
			if value == self.data[m]:
				l = r = m
				continue
			if value < self.data[m]:
				r = m
				continue
			l = m + 1
		if self.data[l] == value:
			self.data.pop(l)

	def get_median(self):
		if len(self.data) == 0:
			return 0
		mid = len(self.data) // 2
		if len(self.data) % 2 == 1:
			return self.data[mid]
		return (self.data[mid - 1] + self.data[mid]) / 2
sortedList = SortedList()
for i in range(d):
	sortedList.insert(ints[i])
notification_count = 0
for i in range(d, n):
	if ints[i] >= 2 * sortedList.get_median():
		notification_count += 1
	sortedList.remove(ints[i - d])
	sortedList.insert(ints[i])
print(notification_count)


import bisect

def notifyClient(expenditures, windowOfDays):
	windowArray = []
	numNotifications = 0
	for idx in range(d):
		bisect.insort(windowArray, expenditures[idx])
	for idx in range(d, len(expenditures)):
		if d % 2 == 0:
			lower = windowArray[int(len(windowArray) / 2)]
			higher = windowArray[int(len(windowArray) / 2 - 1)]
			median = (lower + higher) / 2
		else:
			median = windowArray[int(len(windowArray) / 2)]
		if expenditures[idx] >= 2 * median:
			numNotifications += 1
		toRemove = bisect.bisect(windowArray, expenditures[idx - d]) - 1
		windowArray.pop(toRemove)
		bisect.insort(windowArray, expenditures[idx])
	return numNotifications
(n, d) = input().strip().split(' ')
(n, d) = [int(n), int(d)]
ar = list(map(int, input().split()))
print(notifyClient(ar, d))


def cntmedian(arr, num):
	cur = 0
	i = 0
	while cur + arr[i] < num / 2:
		cur += arr[i]
		i += 1
	if num % 2 == 1 or cur + arr[i] > num / 2:
		return i
	med = i
	i += 1
	while arr[i] == 0:
		i += 1
	return (med + i) / 2
(n, d) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
exp = [0] * 201
last = []
cnt = 0
for i in range(d):
	exp[arr[i]] += 1
	last.append(arr[i])
for i in range(d, n):
	if arr[i] >= 2 * cntmedian(exp, d):
		cnt += 1
	exp[last[0]] -= 1
	exp[arr[i]] += 1
	last.pop(0)
	last.append(arr[i])
print(cnt)