Sam is playing with an array, $\mbox{A}$, of $N$ positive integers. Sam writes a list, $\mbox{S}$, containing all $\mbox{A}$'s contiguous subarrays, and then replaces each subarray with its respective maximum element.

For example, consider the following $\mbox{A}$ where $N=3$: 

$A=\{1,2,3\}$ 

Subarrays of $\mbox{A}$: $S_{initial}=\{\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,2,3\}\}$ 

Updated (Maximum) Subarrays: $S_{maximums}=\{\{1\},\{2\},\{3\},\{2\},\{3\},\{3\}\}$

Help Sam determine how many numbers in $S_{maximums}$ are greater than $\mbox{K}$.

Input Format

The first line contains a single integer, $\mathbf{T}$ (the number of test cases). Each test case is described over two lines: 

The first line of each test case contains two space-separated integers, $N$ (the number of elements in array $\mbox{A}$) and $\mbox{K}$, respectively. 

The second line of each test case contains $N$ space-separated integers describing the elements in $\mbox{A}$.  

Constraints 

$1\leq T\leq10^5$ 

$1\leq N\leq2\times10^5$ 

$1\leq A_i\leq10^9$ 

$0\leq K\leq10^9$ 

$\textit{The sum of N over all test cases does not expressed 10^6}$.  

Output Format

For each test case, print the number of $\textit{maximums}>K$ in $S_{maximums}$ on a new line.

Sample Input
2
3 2
1 2 3 
3 1 
1 2 3 

Sample Output
3
5

Explanation

Both test cases use the same $\mbox{A}$ as described in the Problem Statement, so $S_{maximums}=\{\{1\},\{2\},\{3\},\{2\},\{3\},\{3\}\}$ for both test cases.

Test Case 0: $K=2$ 

$S_{maximums}$ has $3$ elements $>2$, so we print $3$.   

Test Case 1: $K=1$ 

$S_{maximums}$ has $5$ elements ${>1}$, so we print $5$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
def f(a, k):
	bad = 0
	streak = 0
	for x in a:
		if x > k:
			streak = 0
		else:
			streak += 1
			bad += streak
	return len(a) * (len(a) + 1) // 2 - bad
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(f(a, k))


def solve(arr, k):
	left = 0
	n = len(arr)
	res = 0
	for (i, el) in enumerate(arr):
		if el > k:
			res += (n - i) * (left + 1)
			left = 0
		else:
			left += 1
	return res
for _ in range(int(input())):
	(n, k) = [int(s) for s in input().split()]
	arr = [int(s) for s in input().split()]
	print(solve(arr, k))


import sys

def solve(A, K):
	r = None
	c = 0
	for (i, a) in enumerate(A):
		if a > K:
			r = i
			c += i + 1
		elif r != None:
			c += r + 1
		print(c, file=sys.stderr)
	return c
T = int(input())
for _ in range(T):
	(N, K) = (int(_) for _ in input().split())
	A = list((int(_) for _ in input().split()))
	print(solve(A, K))


def main():
	(ncases,) = readints()
	for _ in range(ncases):
		(n, k) = readints()
		a = readints()
		assert n == len(a)
		print(countsubarr(a, k))

def readints():
	return [int(fld) for fld in input().split()]

def countsubarr(a, k):
	ans = len(a) * (len(a) + 1) // 2
	contig = 0
	for elt in a:
		if elt <= k:
			contig += 1
			ans -= contig
		else:
			contig = 0
	return ans
main()


def numSubarraysK(seq, N, K):
	high = [0] + [i + 1 for i in range(N) if next(seq) > K] + [N + 1]
	gaps = [high[i + 1] - high[i] for i in range(0, len(high) - 1)]
	return (sum(gaps) ** 2 - sum((gap ** 2 for gap in gaps))) // 2
num_tests = int(input())
for test in range(num_tests):
	(N, K) = map(int, input().split())
	seq = map(int, input().split())
	print(numSubarraysK(seq, N, K))


t = int(input())
while t > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = n * [0]
	a = input().split()
	a = [int(i) for i in a]
	res = 0
	connc = 0
	for i in range(0, n):
		if a[i] > k:
			connc = i + 1
			res += i + 1
		else:
			res += connc
	print(res)
	t -= 1


T = int(input())
from math import pow

def sigma(n):
	return n * (n + 1) / 2
for i in range(T):
	(N, K) = map(int, input().split())
	xs = list(map(int, input().split()))
	indices = []
	for j in range(N):
		if xs[j] > K:
			indices.append(j + 1)
	r = len(indices)
	result = sum([(N - j + 1) * (j - jpre) for (j, jpre) in zip(indices, [0] + indices)])
	print(int(result))


from collections import deque

def get_max(l, k, n):
	d = deque()
	s = set()
	for i in range(n):
		if l[i] > k:
			d.append(i)
			s.add(i)
	ret = 0
	if d:
		next_idx = d.popleft()
	else:
		next_idx = -1
	for i in range(n):
		if i in s:
			ret += n - i
			if d:
				next_idx = d.popleft()
		elif next_idx > i:
			ret += n - next_idx
	return ret
t = int(input())
for _ in range(t):
	(n, k) = [int(v) for v in input().split()]
	a = [int(v) for v in input().split()]
	print(get_max(a, k, n))


def triangle(n):
	return int(n * (n + 1) / 2)
t = int(input())
for _ in range(t):
	(n, k) = (int(x) for x in input().split())
	a = [int(x) for x in input().split()]
	k_plus_indexes = []
	for (index, item) in enumerate(a):
		if item > k:
			k_plus_indexes.append(index)
	k_plus_indexes = sorted(k_plus_indexes)
	result = 0
	for (index, i) in enumerate(k_plus_indexes):
		left_index = 0
		if index > 0:
			left_index = k_plus_indexes[index - 1] + 1
		left_count = i - left_index + 1
		right_count = n - i
		result += left_count * right_count
	print(result)


def fun(A, n, k):
	cnt = 0
	indices = [-1]
	for (idx, a) in enumerate(A):
		if a > k:
			indices.append(idx)
	indices.append(n)
	for i in range(len(indices) - 1):
		d = indices[i + 1] - indices[i] - 1
		cnt += d * (d - 1) // 2 + d
	total = n * (n - 1) // 2 + n
	return total - cnt
t = int(input())
for i in range(t):
	(n, k) = [int(c) for c in input().split()]
	A = [int(c) for c in input().split()]
	print(fun(A, n, k))


def max_of_subarrays(l, k):
	result = []
	greater_than_k = 0
	mult = 1
	for (i, elem) in enumerate(l):
		if elem > k:
			greater_than_k += mult * (len(l) - i)
			mult = 1
		else:
			mult += 1
	return greater_than_k

def greater_than_k(l, k):
	return len([i for i in l if i > k])
T = int(input())
for i in range(T):
	(N, K) = input().split()
	(N, K) = (int(N), int(K))
	l = [int(i) for i in input().split()]
	print(max_of_subarrays(l, K))


TestCount = int(input())
for test in range(TestCount):
	(ArraySize, BeatThisNumber) = [int(x) for x in input().split()]
	TestArray = [int(x) for x in input().split()]
	LargestCount = 0
	Multiplier = ArraySize
	LastSuccess = -1
	for elem in range(ArraySize):
		if TestArray[elem] > BeatThisNumber:
			if LastSuccess == -1:
				LargestCount += (ArraySize - elem) * (elem + 1)
				Multiplier -= 1
				LastSuccess = elem
			else:
				LargestCount += (ArraySize - elem) * (elem - LastSuccess)
				LastSuccess = elem
	print(LargestCount)


for _ in range(int(input())):
	(N, K) = [int(i) for i in input().split()]
	numbers = [int(i) for i in input().split()]
	total = int(N * (N + 1) / 2)
	count = 0
	newlist = []
	for i in numbers:
		if i <= K:
			count += 1
		elif count > 0:
			newlist.append(count)
			count = 0
	newlist.append(count)
	for i in newlist:
		total -= int(i * (i + 1) / 2)
	print(total)


t = int(input().strip())
for _ in range(t):
	[N, K] = list(map(int, input().strip().split()))
	ar = list(map(int, input().strip().split()))
	ans = N * (N - 1) // 2 + N
	if K == 0:
		print(ans)
	else:
		neg = 0
		i = -1
		while i < N - 1:
			while i < N - 1 and ar[i + 1] > K:
				i += 1
			j = i + 1
			while j < N and ar[j] <= K:
				j += 1
			m = j - i - 1
			neg += m * (m - 1) // 2 + m
			i = j - 1
		ans -= neg
		print(ans)


import sys

def num_greater_K_index(nums, K):
	output = []
	output.append(-1)
	for (i, num) in enumerate(nums):
		if num > K:
			output.append(i)
	output.append(len(nums))
	return output

def subarray_count(n):
	return int(n * (n + 1) / 2)

def number_list():
	(N, K) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	indices = num_greater_K_index(nums, K)
	if len(indices) == 2:
		return 0
	less_count = 0
	for i in range(1, len(indices)):
		less_count += subarray_count(indices[i] - indices[i - 1] - 1)
	return subarray_count(N) - less_count
T = int(input())
for _ in range(T):
	print(number_list())


t = int(input())
for i in range(t):
	(n, k) = [int(j) for j in input().split()]
	l = [int(j) for j in input().split()]
	count = 0
	for j in range(n):
		if l[j] <= k:
			continue
		count += 1
		pos = j - 1
		(c1, c2) = (0, 0)
		while pos != -1 and l[pos] < l[j]:
			c1 += 1
			pos -= 1
		pos = j + 1
		if j != n - 1:
			while l[pos] <= l[j]:
				c2 += 1
				pos += 1
				if pos == n:
					break
		count += c1 + c2 + c1 * c2
	print(count)


T = int(input())
for _ in range(T):
	(N, K) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	result = 0
	for i in range(N):
		if A[i] > K:
			l = 1
			while i - l >= 0 and A[i] >= A[i - l]:
				l += 1
			r = 1
			while i + r < N and A[i] > A[i + r]:
				r += 1
			result += l * r
	print(result)


for _ in range(int(input().strip())):
	paras = [int(i) for i in input().strip().split(' ')]
	nums = [int(i) for i in input().strip().split(' ')]
	count = 0
	counts = []
	while len(nums):
		if nums.pop() > paras[1]:
			if count:
				counts.append(count)
				count = 0
		else:
			count += 1
	if count:
		counts.append(count)
		count = 0
	print((paras[0] + 1) * paras[0] // 2 - sum([(i + 1) * i // 2 for i in counts]))


def SeriesSum(n):
	return int(n * (n + 1) / 2)

def Solve(N, A, K):
	count = SeriesSum(N)
	prev = 0
	for i in range(N):
		if A[i] > K:
			count -= SeriesSum(prev)
			prev = 0
		else:
			prev += 1
	count -= SeriesSum(prev)
	return count

def main():
	T = int(input())
	for t in range(T):
		(N, K) = input().split()
		(N, K) = (int(N), int(K))
		A = input().split()
		A = [int(a) for a in A]
		print(Solve(N, A, K))
main()


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	lis = list(map(int, input().split()))
	res = 0
	l = -1
	for i in range(n):
		if lis[i] > k:
			res += (i - l) * (n - i)
			l = i
	print(res)


from fileinput import input

def find():
	lines = input()
	noc = [int(x) for x in lines[0].strip().split()][0]
	for i in range(noc):
		(n, k) = [int(x) for x in lines[2 * i + 1].strip().split()]
		a = [int(x) for x in lines[2 * i + 2].strip().split()]
		res = 0
		last = -1
		for j in range(n):
			if a[j] > k:
				last = j
			res += last + 1
		print(res, end='\n')
find()


def triangle(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	i = j = num_subarrays = 0
	while i < n:
		while j < n and array[j] <= k:
			j += 1
		num_subarrays += triangle(j - i)
		j += 1
		i = j
	print(triangle(n) - num_subarrays)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split(' '))
	arr = list(map(int, input().strip().split(' ')))
	ans = n * (n + 1) // 2
	flag = 1
	for i in range(n):
		if arr[i] <= k:
			ans -= flag
			flag += 1
		else:
			flag = 1
	print(ans)


from sys import stdin
from itertools import accumulate as acc, count, combinations_with_replacement as cmbrep, takewhile as tkw, repeat as rp, dropwhile as dpw
from functools import reduce
from random import randint
from collections import Counter
from math import sqrt, log
from fractions import gcd
from heapq import merge
from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)
filou = None
if home:
	from mesures import ch, prof
trace = 0
prof = 0
tst = 0

def faster(K, S):
	(offs, pos, cmpt, r) = (-1, 1, len(S), 0)
	pos = 1
	for it in enumerate(S):
		if it[1] <= K:
			pos += 1
			continue
		r += pos * (cmpt - pos + 1)
		cmpt -= pos
		pos = 1
	return r
rd = stdin
for _ in range(int(rd.readline().strip())):
	(N, K) = map(int, rd.readline().strip().split())
	S = list(map(int, rd.readline().strip().split()))
	print(faster(K, S))


def brute(n, k, A):
	total = 0
	for i in range(n):
		ssmax = A[i]
		total += 1 if ssmax > k else 0
		for j in range(i + 1, n):
			ssmax = max(ssmax, A[j])
			if ssmax > k:
				total += 1
	print(total)

def nice(n, k, A):
	total = 0
	LR = [-1 for i in range(n)]
	RL = [-1 for i in range(n)]
	lastKPlus = -1
	for i in range(n):
		if A[i] > k:
			lastKPlus = i
		LR[i] = lastKPlus
	lastKPlus = -1
	for i in range(n - 1, -1, -1):
		if A[i] > k:
			lastKPlus = i
		RL[i] = lastKPlus
	for i in range(n):
		nextKPlus = RL[i]
		if nextKPlus > -1:
			total += n - nextKPlus
	print(total)
t = int(input())
for i in range(t):
	(n, k) = map(int, input().strip().split(' '))
	A = list(map(int, input().strip().split(' ')))
	nice(n, k, A)


def solve(A, K):
	(p, r) = (0, 0)
	for (i, a) in enumerate(A, 1):
		if a > K:
			p = i
		r += p
	return r
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = map(int, input().split())
	print(solve(A, K))


def helper(L, k):
	Tester = [False if x > k else True for x in L]
	N = len(L)
	i = 0
	Total = 0
	run_length = 0
	while i < N:
		if Tester[i]:
			while i < N and Tester[i]:
				run_length += 1
				i += 1
			Total += int(run_length * (run_length + 1) / 2)
			run_length = 0
		i += 1
	return int(N * (N + 1) / 2 - Total)
T = int(input())
for _ in range(T):
	k = int(input().split()[1])
	L = [int(x) for x in input().split()]
	print(helper(L, k))


import sys
tc_len = int(sys.stdin.readline())
for tc in range(tc_len):
	(n, k) = tuple((int(x) for x in sys.stdin.readline().split()))
	a = tuple((int(x) for x in sys.stdin.readline().split()))
	count_from = [-1] * n
	x = -1
	for i in range(n - 1, -1, -1):
		if a[i] > k:
			x = n - i
		count_from[i] = x
	count = 0
	for i in range(n):
		if count_from[i] != -1:
			count += count_from[i]
	print(count)


T = int(input())
for i in range(T):
	(N, K) = (int(j) for j in input().split())
	A = [int(j) for j in input().split()]
	S = [j for j in range(len(A)) if A[j] > K] + [len(A)]
	t = 0
	j = 0
	while j < len(S) - 1:
		t += (S[j] + 1) * (S[j + 1] - S[j])
		j += 1
	print(t)


tests = int(input())
for test in range(tests):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	total = 0
	prevIndex = -1
	for i in range(len(arr)):
		if arr[i] > k:
			prevIndex = i + 1
		if prevIndex > 0:
			total += prevIndex
	print(total)


inf = float('inf')
read_ints = lambda : list(map(int, input().split()))

def solve(N, K, A):
	S = set()
	Ks = [-1]
	for i in range(N):
		if A[i] > K:
			Ks.append(i)
	ans = 0
	for i in range(1, len(Ks)):
		left_size = Ks[i] - Ks[i - 1]
		right_size = N - Ks[i]
		ans += left_size * right_size
	return ans
T = int(input())
for _ in range(T):
	(N, K) = read_ints()
	A = read_ints()
	print(solve(N, K, A))


import itertools

def find_all_subgroups(A, N, K):
	res = []
	for i in range(1, len(A) + 1):
		lst = itertools.combinations(A, i)
		res.extend(list(lst))
	return res

def find_result(A, N, K):
	all_groups = find_all_subgroups(A, N, K)
	print(all_groups)
	S = [max(i) for i in all_groups]
	S1 = [i for i in S if i > K]
	return len(S1)

def numberList(a, k):
	result = 0
	last_biggest = -1
	a_len = len(a)
	for idx in range(a_len):
		if a[idx] > k:
			result += (idx - last_biggest) * (a_len - idx)
			last_biggest = idx
	return result
T = int(input())
for _ in range(T):
	(N, K) = input().split()
	(N, K) = (int(N), int(K))
	A = input().split()
	A = [int(i) for i in A]
	res = numberList(A, K)
	print(res)


T = int(input())
for t0 in range(T):
	(N, K) = (int(a) for a in input().split())
	A = [int(a) for a in input().split()]
	s = 0
	l = -1
	for (i, a) in enumerate(A):
		if a > K:
			l = i
		if l > -1:
			s += l + 1
	print(s)


t = int(input())
for i in range(t):
	L = list(map(int, input().split()))
	n = L[0]
	k = L[1]
	L = list(map(int, input().split()))
	l = 0
	s = 0
	p = 1
	for j in range(len(L)):
		if L[j] <= k:
			s += p
			p += 1
		if L[j] > k:
			p = 1
	print(int(n * (n + 1) / 2 - s))


t = int(input())
for it in range(t):
	(n, k) = [int(x) for x in input().split()]
	ret = n * (n + 1) // 2
	count = 1
	is_less_than_k = True
	vals = [int(x) for x in input().split()]
	for val in vals:
		if val > k:
			is_less_than_k = False
		else:
			if not is_less_than_k:
				is_less_than_k = True
				count = 1
			ret -= count
			count += 1
	print(ret)


t = int(input())
for _ in range(t):
	(number, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	res = number * (number + 1) // 2
	start = 0
	end = 0
	while end < number:
		if l[end] > k:
			res -= (end - start + 1) * (end - start) // 2
			start = end + 1
		end += 1
	res -= (end - start + 1) * (end - start) // 2
	print(res)


T = int(input())
for run in range(T):
	(n, k) = [int(i) for i in input().split()]
	num = [int(i) for i in input().split()]
	dp = [0] * n
	for i in range(n):
		if num[i] > k:
			dp[i] = i + 1
		elif i > 0:
			dp[i] = dp[i - 1]
	print(sum(dp))


cases = int(input())
for case in range(cases):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	(result, follow) = (0, 0)
	for (i, num) in enumerate(a):
		follow = i + 1 if num > k else follow
		result += follow
	print(result)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().strip().split(' '))
	a = list(map(int, input().strip().split(' ')))
	count = 0
	index = [-1]
	for i in range(n):
		if a[i] > k:
			index.append(i)
	num = 0
	for i in range(1, len(index)):
		num += (index[i] - index[i - 1]) * (n - index[i])
	print(num)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	d = list(map(int, input().split()))
	res = n * (n + 1) // 2
	i = 0
	while i < len(d):
		j = 0
		while i + j < len(d) and d[i + j] <= k:
			j += 1
		res -= j * (j + 1) // 2
		j += 1
		i += j
	print(res)


def merge_count(A, K):
	if len(A) > 0:
		max_index = 0
		for i in range(0, len(A)):
			if A[max_index] < A[i]:
				max_index = i
		if A[max_index] > K:
			return (max_index + 1) * (len(A) - max_index) + merge_count(A[0:max_index], K) + merge_count(A[max_index + 1:len(A)], K)
		else:
			return 0
	else:
		return 0
T = int(input())
for _ in range(0, T):
	(N, K) = [int(a) for a in input().split()]
	A = [int(a) for a in input().split()]
	print(merge_count(A, K))


def f(n):
	return n * (n + 1) // 2
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	(total, seq) = (0, 0)
	for a in A:
		if a > K:
			total += f(seq)
			seq = 0
		else:
			seq += 1
	total += f(seq)
	print(N * (N + 1) // 2 - total)


def main():
	T = int(input())
	for _ in range(T):
		(N, K) = map(int, input().split())
		A = list(map(int, input().split()))
		res = N * (N + 1) // 2
		j = -1
		for i in range(N):
			if A[i] > K:
				j = i
			else:
				res -= i - j
		print(res)
main()


T = int(input())
for tmp in range(T):
	[N, K] = list(map(int, input().strip().split(' ')))
	arr = list(map(int, input().strip().split(' ')))
	m = [-1] + list((idx for (idx, value) in enumerate(arr) if value > K)) + [N]
	s = 0
	for idx in range(len(m) - 1):
		l = m[idx + 1] - m[idx] - 1
		s += l * (l + 1) // 2
	print(N * (N + 1) // 2 - s)


def f(a, k):
	bad = 0
	streak = 0
	for x in a:
		if x > k:
			streak = 0
		else:
			streak += 1
			bad += streak
	return len(a) * (len(a) + 1) // 2 - bad
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(f(a, k))


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


import sys

def solve_bf(aa, k):
	print('k=%d aa=%s' % (k, aa), file=sys.stderr)
	cnt = 0
	for fr in range(len(aa)):
		for to in range(fr + 1, len(aa) + 1):
			m = max(aa[fr:to])
			if m > k:
				cnt += 1
	return cnt

def solve(aa, k):
	print('k=%d aa=%s' % (k, aa), file=sys.stderr)
	ii = [i for (i, a) in enumerate(aa) if a > k]
	print('\tii=%s' % ii, file=sys.stderr)
	(cnt, last) = (0, -1)
	for i in ii:
		delta = (i - last) * (len(aa) - i)
		cnt += delta
		last = i
	return cnt
t = int(input())
for _ in range(t):
	(_, k) = map(int, input().split())
	aa = list(map(int, input().split()))
	print(solve(aa, k))


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	A = [int(x) for x in input().split()]
	c = N * (N + 1) // 2
	i = 0
	for x in A:
		if x > K:
			i = 0
		else:
			i += 1
			c -= i
	print(c)


num_probs = int(input())
for _ in range(num_probs):
	(n, k) = (int(x) for x in input().split())
	A = [int(x) for x in input().split()] + [k + 1]
	count = 0
	prev = -1
	for i in range(n + 1):
		if A[i] > k:
			delta = i - prev
			count += delta * (delta - 1) // 2
			prev = i
	print(n * (n + 1) // 2 - count)


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


from math import *
mod = 1000000007

def binpow(a, b):
	global mod
	if b == 1:
		return a % mod
	u = binpow(a, b // 2)
	if b % 2 == 0:
		return u * u % mod
	else:
		return u * u * a % mod
dic = {}

def ncr(n, r):
	if r > n - r:
		r = n - r
	if r == 0 and n == 0:
		return 1
	if r > n:
		return 0
	if n == r or r == 0:
		return 1
	if r == 1:
		return n
	key = str(n) + '|' + str(r)
	if key not in dic:
		dic[key] = ncr(n - 1, r - 1) + ncr(n - 1, r)
	return dic[key]
for _ in range(int(input())):
	s = [int(i) for i in input().split()]
	(n, k) = (s[0], s[1])
	arr = [int(i) for i in input().split()]
	l = []
	for i in range(n):
		if arr[i] > k:
			l.append(i)
	total = 0
	for x in range(len(l)):
		if not x == len(l) - 1:
			total += (l[x] + 1) * (l[x + 1] - l[x])
		else:
			total += (l[x] + 1) * (n - l[x])
	print(total)


for x in range(int(input())):
	(a, b) = (0, 1)
	nk = list(map(int, input().split()))
	n = list(map(int, input().split()))
	t = nk[0]
	for y in range(len(n)):
		if n[y] <= nk[1]:
			a += b
			b += 1
		else:
			b = 1
	print(t * (t + 1) // 2 - a)


def numberList(a, k):
	result = 0
	last_biggest = -1
	a_len = len(a)
	for idx in range(a_len):
		if a[idx] > k:
			result += (idx - last_biggest) * (a_len - idx)
			last_biggest = idx
	return result
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(numberList(a, k))


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


import os
import sys
for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


import os
import sys
for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)


for a0 in range(int(input())):
	x = [int(y) for y in input().split()]
	(n, k) = (x[0], x[1])
	ar = [int(y) for y in input().split()]
	s = n
	b = []
	for i in range(n):
		if ar[i] > k:
			b.append(s)
		s -= 1
	first = 0
	if len(b) == 0:
		print(0)
		continue
	total = 0
	for i in range(n):
		if ar[i] <= k:
			total += b[first]
		elif ar[i] > k:
			total += b[first]
			first += 1
			if first == len(b):
				break
	print(total)