Read problem statements in [Mandarin], [Russian], and [Vietnamese] as well.

You are given a sequence of integers A_{1}, A_{2}, \ldots, A_{N} and an integer K. Find the number of contiguous subsequences A_{L}, A_{L+1}, \ldots, A_{R} such that R-L+1 ≥ K and the K-th element of the subsequence (A_{L+K-1}) is equal to the maximum of all elements of the entire sequence.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N and K.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each test case, print a single line containing one integer --- the number of contiguous subsequences satisfying the given conditions.

------ Constraints ------ 

$1 ≤T ≤200$
$1 ≤K ≤N ≤2 \cdot 10^{5}$
$|A_{i}| ≤10^{5}$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

------ subtasks ------ 

Subtask #1 (10 points)
$T ≤10$
$N ≤100$

Subtask #2 (90 points) original constraints

----- Sample Input 1 ------ 
1
5 3
1 2 3 4 5
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
Example case 1: $(3, 4, 5)$ is the only contiguous subsequence such that its $3$-rd element is equal to the maximum of the whole sequence (which is $5$).

Difficulty: MEDIUM
Tags: Constructive algorithms

Combinatorics

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	list1 = [int(x) for x in input().split()]
	max1 = max(list1)
	ans = 0
	for i in range(n):
		if list1[i] == max1 and i >= k - 1:
			ans += 1
			ans += n - 1 - i
	print(ans)


test = int(input())
for z in range(test):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	M = max(A)
	ans = 0
	for i in range(n):
		if A[i] == M and i >= k - 1:
			ans += 1
			ans += n - 1 - i
	print(ans)


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


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = max(l)
	count = 0
	for i in range(k - 1, n):
		if l[i] == x:
			count = count + (n - i)
	print(count)


import os, sys, io, math
from array import *
from math import *
from bisect import *
from heapq import *
from functools import *
from itertools import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, k) = map(int, input().split())
	l = I()
	(r, s, m) = (0, 0, max(l))
	for i in range(l.count(m)):
		t = l.index(m, s)
		if t >= k - 1:
			r += n - t
		s = t + 1
	print(r)


def k_subseq(a, n, k):
	max_n = max(a)
	final_sub_n = 0
	prev_n = 0
	for i in range(a.count(max_n)):
		cur = a.index(max_n, prev_n)
		if cur >= k - 1:
			final_sub_n += n - cur
		prev_n = cur + 1
	return final_sub_n
for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(k_subseq(a, n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	y = max(x)
	count = 0
	for j in range(k - 1, len(x)):
		if y == x[j]:
			count += n - j
	print(count)


def solution():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(mx, ans, k) = (max(arr), 0, k - 1)
	for i in range(n):
		if arr[i] == mx and i >= k:
			ans += n - i
	print(ans)
for _ in range(int(input())):
	solution()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	cnt = 0
	res = max(arr)
	for i in range(k - 1, n):
		if arr[i] == res:
			cnt += n - i
		else:
			cnt = cnt
	print(cnt)


from bisect import bisect_left, bisect_right
import math
from sys import maxsize
from collections import defaultdict
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	(n, k) = il()
	num = il()
	ans = 0
	mx = max(num)
	for i in range(k - 1, n):
		if num[i] == mx:
			ans += n - i
	print(ans)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	maximum = max(l)
	ans = 0
	for i in range(len(l)):
		point = -1
		if l[i] == maximum:
			if i - m + 1 > -1:
				point = i
		if point == -1:
			ans += 0
		else:
			ans += len(l) - i
	print(ans)


from sys import stdin
ip = stdin.readline
from collections import Counter
for _ in range(int(ip())):
	(n, k) = map(int, ip().split())
	ar = list(map(int, ip().split()))
	ans = 0
	mx = max(ar)
	for (i, x) in enumerate(ar):
		if x == mx:
			if i - k + 1 >= 0:
				ans += n - i
	print(ans)


def soln(n, k, arr):
	maxm = max(arr)
	res = 0
	for i in range(k - 1, n):
		if arr[i] == maxm:
			res += n - i
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(soln(n, k, arr))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = max(a)
	count = 0
	for i in range(k - 1, n):
		if a[i] == m:
			count += n - i
	print(count)


for t in range(int(input())):
	(N, K) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	c = 0
	maxi = max(A)
	for i in range(K - 1, N):
		if A[i] == maxi:
			c += N - i
		else:
			c += 0
	print(c)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	maxv = max(a)
	ans = 0
	for i in range(k - 1, n):
		if a[i] == maxv:
			ans = ans + n - i
		else:
			ans = ans + 0
	print(ans)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 0
	maxVal = max(A)
	indices = [ind for (ind, ele) in enumerate(A) if ele == maxVal]
	for i in indices:
		if i >= k - 1:
			ans += n - i
	print(ans)


def solve():
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	Mx = max(lis)
	ans = 0
	for i in range(k - 1, n):
		if lis[i] == Mx:
			ans += n - i
	print(ans)
for _ in range(int(input())):
	solve()


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr: enumerate(itr)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def solve(*args, **kwargs):
	((n, k), arr) = args
	(max_, max_idx) = (max(arr), [])
	for (idx, ele) in enum(arr):
		if ele != max_:
			continue
		max_idx.append(idx)
	return sum((n - idx for idx in max_idx if idx - k + 1 >= 0))

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg2 = inp_vars(int, SPACE)
		arg3 = inp_vars(int, SPACE)
		res = solve(*(arg2, arg3))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	Ai = list(map(int, input().split()))
	m = max(Ai)
	sume = 0
	for i in range(n + 1 - k):
		if Ai[i - 1 + k] == m:
			sume += n - (i + k) + 1
	print(sume)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	j = max(a)
	ans = 0
	for i in range(k - 1, n):
		if a[i] == j:
			ans += n - i
	print(ans)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	n = max(a)
	c = 0
	for i in range(y - 1, len(a)):
		if a[i] == n:
			c += len(a) - i
	print(c)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = max(a)
	count = 0
	for j in range(len(a)):
		if a[j] == d and j >= k - 1:
			count += n - j
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mx = max(a)
	i = k - 1
	ans = 0
	while i < n:
		if a[i] == mx:
			ans += n - i
		i += 1
	print(ans)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	max1 = max(li)
	count = 0
	for i in range(k - 1, n):
		if max1 == li[i]:
			count += n - i
	print(count)
	t -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = max(l)
	a = 0
	for i in range(n):
		if l[i] == m and i + 1 >= k:
			a += n - i
	print(a)


t = int(input())
for i in range(t):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	m = max(A)
	a = 0
	for i in range(N):
		if A[i] == m and i + 1 >= K:
			a += N - i
	print(a)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	maxx = max(list1)
	counter = 0
	for i in range(n):
		if list1[i] == maxx:
			if i >= k - 1:
				counter += n - i
	print(counter)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	k = inputs[1]
	list1 = [int(num) for num in input().split()]
	maxi = 0
	max1 = list1[0]
	for i in range(0, len(list1)):
		if list1[i] > max1:
			maxi = i
			max1 = list1[i]
	maxindices = []
	for i in range(0, len(list1)):
		if list1[i] == max1:
			maxindices.append(i)
	no_of_elements_before_max = maxi
	c = 0
	for i in range(0, len(maxindices)):
		maxi = maxindices[i]
		if maxi >= k - 1:
			no_of_elements_after_max = n - (maxi + 1)
			c += no_of_elements_after_max + 1
	print(c)


n = int(input())
for i in range(n):
	(N, K) = [int(x) for x in input().split(' ')]
	arr = [int(x) for x in input().split(' ')]
	cnt = 0
	maxele = max(arr)
	for i in range(K - 1, N):
		if arr[i] == maxele:
			cnt += N - i
	print(cnt)


def function(Input):
	for _ in range(Input):
		(N, K) = map(int, input().split())
		array = list(map(int, input().split()))
		counter = 0
		arrgmax = max(array)
		for i in range(K - 1, N):
			if array[i] == arrgmax:
				counter += N - i
		print(counter)
	return ' '
Input = int(input())
a = function(Input)
print(a)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	maxEle = max(arr)
	c = 0
	for i in range(k - 1, n):
		if arr[i] == maxEle:
			c += n - i
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	a = max(arr)
	sum = 0
	for i in range(k - 1, n):
		if arr[i] == a:
			sum += n - i
	print(sum)


t = int(input())
for q in range(t):
	(n, k) = map(int, input().split())
	N = list(map(int, input().split()))
	count = 0
	maxi = max(N)
	for l in range(k - 1, n):
		if N[l] == maxi:
			count += n - l
	print(count)


T = int(input())
for tc in range(T):
	(N, K) = map(int, input().split())
	A = [int(i) for i in input().split()]
	ans = 0
	if len(A) == N:
		mx = max(A)
		for i in range(K - 1, N):
			if A[i] == mx:
				ans = ans + N - i
		print(ans)
	else:
		break


try:
	for i in range(int(input())):
		(n, k) = map(int, input().split(' '))
		l = list(map(int, input().split(' ')))
		count = 0
		left = 0
		m = max(l)
		for i in range(n):
			if i - left + 1 == k:
				if l[left + k - 1] == m:
					count += n - i
				left += 1
		print(count)
except Exception:
	pass


from random import randrange
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	maxi = max(a)
	mxind = [i for (i, x) in enumerate(a) if x == maxi and i >= k - 1]
	ans = 0
	for i in range(len(mxind)):
		if mxind[i] >= k - 1:
			ans += 1
			ans += n - (mxind[i] + 1)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nli = list(map(int, input().split()))
	mx = max(nli)
	mxind = [i for (i, x) in enumerate(nli) if x == mx and i >= k - 1]
	ans = 0
	for i in range(len(mxind)):
		if mxind[i] >= k - 1:
			ans += 1
			ans += n - (mxind[i] + 1)
	print(ans)


for _ in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	arr = list(map(int, input().split()))
	maxValue = max(arr)
	maxIndices = []
	for (i, element) in enumerate(arr):
		if element == maxValue:
			maxIndices.append(i)
	counter = 0
	for index in maxIndices:
		if index + 1 < k:
			continue
		else:
			counter += n - index
	print(counter)


t = int(input())
for z in range(t):
	c = 0
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = max(a)
	for i in range(k - 1, n):
		if a[i] == m:
			c = c + n - i
	print(c)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	maxi = max(l)
	ans = 0
	for i in range(n):
		if l[i] == maxi and i >= k - 1:
			ans += n - i
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	m = max(a)
	for x in range(n - k + 1):
		if a[x + k - 1] == m:
			c += n - (x + k - 1)
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 0
	m = max(A)
	for i in range(k - 1, n):
		if A[i] == m:
			ans += n - i
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().strip().split()))
	mx = max(a)
	c = 0
	for i in range(n):
		if a[i] == mx and i + 1 >= k:
			c += n - i
	print(c)


try:
	for t in range(int(input())):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		count = 0
		maximum = max(A)
		for i in range(K - 1, N):
			if A[i] == maximum:
				count += N - i
		print(count)
except:
	pass


def kthmax(n, k, arr):
	m1 = max(arr)
	ans = 0
	for i in range(k - 1, n):
		if arr[i] == m1:
			ans += n - i
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(kthmax(n, k, arr))


import math
for q in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	arr = []
	max1 = 0
	sum1 = 0
	for i in range(n):
		if max1 < a[i]:
			max1 = a[i]
	for i in range(k - 1, n):
		if a[i] == max1:
			sum1 += n - (i + 1) + 1
	print(sum1)


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	mx = max(a)
	for i in range(k - 1, n):
		if a[i] == mx:
			count += n - i
	print(count)


for _ in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	ans = 0
	maxx = max(l)
	for i in range(b - 1, a):
		c = 0
		if l[i] == maxx:
			c = 1
			c += a - 1 - i
		ans += c
	print(ans)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	ele = max(s)
	a = 0
	for i in range(n):
		if s[i] == ele and i + 1 >= k:
			a += n - i
	print(a)


def solve(arr, n, k):
	ans = [0]
	ind = 0
	for i in range(1, n):
		if arr[i] > arr[ind]:
			ans = [i]
			ind = i
		elif arr[i] == arr[ind]:
			ans.append(i)
	res = 0
	for x in ans:
		if x >= k - 1:
			res += n - x
	return res
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(solve(arr, n, k))


from collections import *
for u in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	m = max(l)
	for i in range(k - 1, n):
		if l[i] == m:
			c += n - i
	print(c)


for _ in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	a = list(map(int, input().split()))
	max_a = 0
	for i in a:
		if i > max_a:
			max_a = i
	count = 0
	for i in range(k - 1, len(a)):
		if a[i] == max_a:
			count += n - i
	print(count)


test = int(input())
for i in range(0, test):
	(n, k) = map(int, input().split(' '))
	array = list(map(int, input().split()))
	answer = 0
	maax = max(array)
	for i in range(k - 1, n):
		if array[i] == maax:
			answer += n - i
	print(answer)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()][:n]
	m = max(a)
	c = 0
	ind = a.index(max(a))
	for j in range(n):
		if a[j] == m and j + 1 >= k:
			c = c + (n - j)
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	maxx = max(l)
	ans = 0
	for i in range(k - 1, n):
		if l[i] == maxx:
			ans += n - i
	print(ans)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	list1 = list(map(int, input().split()))
	big = max(list1)
	count = 0
	for j in range(K - 1, N):
		if list1[j] == big:
			count += N - j
	print(count)


def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	maxi = max(arr)
	ans = 0
	for i in range(k - 1, len(arr)):
		if maxi == arr[i]:
			ans += n - i
	return ans
t = int(input())
while t:
	print(solve())
	t -= 1