ChefTown is the biggest city and the capital of ChefLand. There are N beautiful buildings: restaurants, museums, living houses with large kitchens and so on. Every building has its height. For every i (1≤i≤N) there is exactly one building with height i. The buildings are located in a single line from left to right. The height of ith building is H(i). The Mayor of ChefTown wants to organize a parade, where all great chefs will take part. A parade depends of its location. The location of a parade is a segment of consecutive buildings beginning near the building number L and ending near the building number R (1≤L≤R≤N). Any parade won't be interesting if it is not hold on an interesting segment of buildings. The segment of buildings is interesting if following are hold:

Imagine, that we have a segment [L,R].
Let K=R-L+1 be the length of this segment, and B be a list of heights of the buildings that belong to this segment.
Let's sort B in non-decreasing order.
Segment [L,R] is interesting if B[i]-B[i-1]=1 for every i (2≤i≤K).

Now the Mayor of ChefTown is interested how many ways to organize an interesting parade of length W for ChefTown citizens. Help him and find out the number of different parades of length W, which can be hold in the city. Two parades ([L1,R1] and [L2,R2]) are considered to be different, if L1≠L2 or R1≠R2.

------ Input ------ 

Each input file consists of two lines, the first one contains two integers N and W (1≤N≤400000, 1≤W≤N). The second line contains N numbers H(i) (1≤i≤N) - the heights of the buildings. 

------ Output ------ 

For each test case output a single integer - the number of interesting segments of buildings of length W.

----- Sample Input 1 ------ 
2 1
2 1
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 

----- Sample Input 2 ------ 
4 2
1 2 3 4
----- Sample Output 2 ------ 
3
----- explanation 2 ------

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Mathematics


Solutions:
from collections import deque
(n, w) = map(int, input().split())
l = list(map(int, input().split()))
(d, e) = (deque(), deque())
for i in range(w):
	while len(d) > 0 and d[-1] > l[i]:
		d.pop()
	while len(e) > 0 and e[-1] < l[i]:
		e.pop()
	d.append(l[i])
	e.append(l[i])
ans = 0
for i in range(w, n):
	if e[0] - d[0] + 1 == w:
		ans += 1
	curr = l[i - w]
	if curr == d[0]:
		d.popleft()
	if curr == e[0]:
		e.popleft()
	while len(d) > 0 and d[-1] > l[i]:
		d.pop()
	while len(e) > 0 and e[-1] < l[i]:
		e.pop()
	d.append(l[i])
	e.append(l[i])
if e[0] - d[0] + 1 == w:
	ans += 1
print(ans)


(n, k) = map(int, input().split())
arr = [int(_) for _ in input().split()]
ans = 0
if k == 1:
	print(n)
else:
	deq = [0 for _ in range(n)]
	minarr = [0 for _ in range(n - k + 1)]
	maxarr = [0 for _ in range(n - k + 1)]
	q_st = q_size = 0
	for i in range(n):
		while q_size > 0 and deq[q_st + q_size - 1] > arr[i]:
			q_size -= 1
		deq[q_st + q_size] = arr[i]
		q_size += 1
		if i >= k and arr[i - k] == deq[q_st]:
			q_st += 1
			q_size -= 1
		if i >= k - 1:
			minarr[i - k + 1] = deq[q_st]
	q_st = q_size = 0
	for i in range(n):
		while q_size > 0 and deq[q_st + q_size - 1] < arr[i]:
			q_size -= 1
		deq[q_st + q_size] = arr[i]
		q_size += 1
		if i >= k and arr[i - k] == deq[q_st]:
			q_st += 1
			q_size -= 1
		if i >= k - 1:
			maxarr[i - k + 1] = deq[q_st]
	ans = 0
	for i in range(n - k + 1):
		if maxarr[i] - minarr[i] == k - 1:
			ans += 1
	print(ans)


(n, w) = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]
(sm, sqrsm, ans) = (0, 0, 0)
b = w * (w - 1) // 2
a = w * (w - 1) * (2 * w - 1) // 6
for i in range(w):
	sm += nums[i]
	sqrsm += nums[i] ** 2
if (sm - b) % w == 0:
	x = (sm - b) // w
	if sqrsm == w * x * x + a + 2 * x * b:
		ans += 1
for i in range(w, n):
	sm += nums[i] - nums[i - w]
	sqrsm += nums[i] ** 2 - nums[i - w] ** 2
	if (sm - b) % w == 0:
		x = (sm - b) // w
		if sqrsm == w * x * x + a + 2 * x * b:
			ans += 1
print(ans)