"It does not matter how slowly you go as long as you do not stop." - Confucius
You are given an array $A_1, A_2, \ldots, A_N$ and an integer $K$. For each subarray $S = [A_l, A_{l+1}, \ldots, A_r]$ ($1 \le l \le r \le N$):
- Let's define an array $B$ as $S$ concatenated with itself $m$ times, where $m$ is the smallest integer such that $m(r-l+1) \ge K$.
- Next, let's sort $B$ and define $X = B_K$, i.e. as a $K$-th smallest element of $B$. Note that $|B| \ge K$.
- Then, let's define $F$ as the number of occurrences of $X$ in $S$.
- The subarray $S$ is beautiful if $F$ occurs in $S$ at least once.
Find the number of beautiful subarrays of $A$. Two subarrays $A_l, A_{l+1}, \ldots, A_r$ and $A_p, A_{p+1}, \ldots, A_q$ are different if $l \neq p$ or $r \neq q$.

-----Input-----
- 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-----
For each test case, print a single line containing one integer - the number of beautiful subarrays.

-----Constraints-----
- $1 \le T \le 5$
- $1 \le N \le 2,000$
- $1 \le K \le 10^9$
- $1 \le A_i \le 2000$ for each valid $i$

-----Subtasks-----
Subtask #1 (20 points): $1 \le N \le 200$
Subtask #2 (80 points): original constraints

-----Example Input-----
1
3 3
1 2 3

-----Example Output-----
3

-----Explanation-----
Example case 1: There are six subarrays of $A$: $[1]$, $[2]$, $[3]$, $[1, 2]$, $[2, 3]$, $[1, 2, 3]$. The corresponding arrays $B$ are $[1, 1, 1]$, $[2, 2, 2]$, $[3, 3, 3]$, $[1, 2, 1, 2]$, $[2, 3, 2, 3]$, $[1, 2, 3]$.
Three of the subarrays are beautiful: $[1]$, $[1, 2]$ and $[1, 2, 3]$. For these subarrays, $X$ is $1$, $2$ and $3$ respectively (for example, for $S = [1, 2]$, $B = [1, 2, 1, 2]$ is sorted to $[1, 1, 2, 2]$ and $X = 2$ is the $3$-rd element). Then, $F = 1$ for each of these subarrays, and each of these subarrays contains $1$.

Source: codechef | Difficulty: HARD
Tags: Sorting

Range queries

Segment trees revisited


Solutions:
import bisect
import math
t = int(input())
while t > 0:
	fp = 0
	(n, k) = map(int, input().split())
	a = [int(o) for o in input().split()]
	for i in range(n):
		left = []
		arr = [0] * 2050
		for j in range(i, n):
			right = a[j]
			bisect.insort(left, right)
			arr[a[j]] += 1
			uhoy = math.ceil(k / (j - i + 1))
			mc = int(math.ceil(k / uhoy))
			kpop = arr[left[mc - 1]]
			if arr[kpop] >= 1:
				fp += 1
	print(fp)
	t -= 1


import math
import heapq

def counting_sort(array1, max_val):
	m = max_val + 1
	count = [0] * m
	for a in array1:
		count[a] += 1
	i = 0
	for a in range(m):
		for c in range(count[a]):
			array1[i] = a
			i += 1
	return array1
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	M = []
	ans = 0
	for i in range(n):
		for j in range(i, n):
			m = math.ceil(k / (j - i + 1))
			gt = (k - 1) // m
			M.append(gt)
		break
	for i in range(n):
		max = -1
		s = set()
		d = {}
		hallo_frnd = {}
		for j in range(i, n):
			x = None
			value = M[j - i]
			if l[j] not in d:
				d[l[j]] = 1
			else:
				d[l[j]] += 1
			if l[j] > max:
				max = l[j]
			if value not in s:
				s.add(value)
				x = max
				hallo_frnd[value] = max
			elif l[j] < hallo_frnd[value]:
				yt = l[i:j + 1]
				heapq.heapify(yt)
				x = heapq.nsmallest(value + 1, yt)[-1]
				hallo_frnd[value] = x
			else:
				x = hallo_frnd[value]
			if d[x] in d:
				ans += 1
	print(ans)


from math import ceil

def Beauty(array, f, n):
	i = 0
	j = i
	ans = 0
	while i < n and j < n:
		if array[j] == f:
			ans += (n - j) * (j - i) + (n - j)
			i = j + 1
			j = i
		else:
			j += 1
	return ans
from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	s = defaultdict(int)
	for v in array:
		s[v] += 1
	res = 0
	for i in range(n):
		for j in range(i, n):
			b = array[i:j + 1]
			b.sort()
			m = ceil(k / (j - i + 1))
			t = ceil(k / m)
			x = b[t - 1]
			f = b.count(x)
			if f in b:
				res += 1
	print(res)


import sys
input = sys.stdin.readline
from collections import defaultdict
from math import ceil
from bisect import bisect_left as bl, insort
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	ans = 0
	for i in range(n):
		curr = []
		cnt = [0] * 2002
		for j in range(i, n):
			add = ceil(k / (j - i + 1))
			insort(curr, l[j])
			cnt[l[j]] += 1
			if k <= j - i + 1:
				x = curr[k - 1]
			else:
				x = curr[ceil(k / add) - 1]
			z = cnt[x]
			if cnt[z]:
				ans += 1
	print(ans)


import bisect as b
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		x = [0]
		for j in range(i, n):
			b.insort(x, a[j])
			y = k / (len(x) - 1)
			if int(y) != y:
				y = int(y) + 1
			y = int(y)
			z = k / y
			if int(z) != z:
				z = int(z) + 1
			z = int(z)
			if x.count(x[z]) in x:
				c += 1
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	from math import ceil
	l = [int(i) for i in input().split()]
	cnt = 0
	for i in range(n):
		for j in range(i, n):
			add = ceil(k / (j - i + 1))
			curr = l[i:j + 1]
			curr.sort()
			if k <= j - i + 1:
				x = curr[k - 1]
			else:
				x = curr[ceil(k / add) - 1]
			z = curr.count(x)
			if z in curr:
				cnt += 1
	print(cnt)


from math import ceil
from bisect import insort
t = int(input())
for i in range(t):
	c = 0
	(n, k) = map(int, input().split())
	L = list(map(int, input().split()))
	for u in range(n):
		l = []
		cont = [0] * 2001
		for j in range(u, n):
			insort(l, L[j])
			cont[L[j]] += 1
			m = ceil(k / len(l))
			x = ceil(k / m)
			f = cont[l[x - 1]]
			if cont[f] != 0:
				c = c + 1
	print(c)


from math import ceil
from bisect import insort
for z in range(int(input())):
	(N, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	i = 0
	pos = []
	while i < N:
		pos.append(ceil(k / ceil(k / (i + 1))))
		i += 1
	i = 0
	while i < N - 1:
		h = []
		cl = [0] * 2001
		j = 0
		while i + j < N:
			cl[a[i + j]] += 1
			insort(h, a[i + j])
			x = h[pos[j] - 1]
			f = cl[x]
			if cl[f]:
				c += 1
			j += 1
		i += 1
	print(c)


import bisect
import math
for _ in range(int(input().strip())):
	(n, k) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	inds = []
	for i in range(1, 2001):
		inds.append(math.ceil(k / math.ceil(k / i)) - 1)
	cnt = 0
	for i in range(n):
		subArray = []
		frequencies = [0] * 2001
		for j in range(i, n):
			bisect.insort(subArray, arr[j])
			frequencies[arr[j]] += 1
			if subArray[0] <= len(subArray):
				x = subArray[inds[len(subArray) - 1]]
				f = frequencies[x]
				if frequencies[f] != 0:
					cnt += 1
	print(cnt)


from math import ceil
from bisect import insort
t = int(input())
for test in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		b = list()
		d = dict()
		for j in range(i, n, 1):
			if a[j] in d:
				d[a[j]] += 1
			else:
				d[a[j]] = 1
			insort(b, a[j])
			x = b[ceil(k / ceil(k / (j - i + 1))) - 1]
			f = d[x]
			if f in d:
				ans += 1
	print(ans)


import bisect
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	count = 0
	for i in range(n):
		c = [0 for x in range(n + 1)]
		d = []
		for j in range(i, n):
			bisect.insort(d, a[j])
			c[a[j]] += 1
			req = c[d[(k - 1) // ((k - 1) // (j - i + 1) + 1)]]
			if c[req] > 0:
				count += 1
	print(count)


import bisect
t = int(input())
while t > 0:
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	m = 0
	p = 0
	ans = 0
	pos = [0] * (n + 1)
	for i in range(1, n + 1):
		if k % i == 0:
			m = k // i
		else:
			m = k // i + 1
		if k % m == 0:
			p = k // m
		else:
			p = k // m + 1
		pos[i] = p - 1
	for i in range(0, n):
		res = {}
		sub = []
		for j in range(i, n):
			if res.get(arr[j], -1) == -1:
				res[arr[j]] = 1
			else:
				res[arr[j]] += 1
			bisect.insort(sub, arr[j])
			x = sub[pos[j - i + 1]]
			f = res[x]
			if res.get(f, -1) == -1:
				ans = ans
			else:
				ans += 1
	print(ans)
	t = t - 1


from collections import defaultdict
from math import ceil
import heapq
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	temp = []
	beautiful = 0
	freq = [0] * 2001
	for i in range(n):
		freq = [0] * 2001
		alpha_old = 1
		temp = []
		reserve = []
		freq[arr[i]] = 1
		heapq.heappush(temp, -arr[i])
		if arr[i] == 1:
			beautiful = beautiful + 1
		flag = False
		for j in range(i + 1, n):
			freq[arr[j]] = freq[arr[j]] + 1
			if flag:
				if arr[j] < -temp[0]:
					heapq.heapreplace(temp, -arr[j])
				if freq[freq[-temp[0]]] != 0:
					beautiful = beautiful + 1
				continue
			s = j - i + 1
			alpha_new = ceil(k / ceil(k / s))
			if alpha_new != alpha_old:
				for x in reserve:
					heapq.heappush(temp, -x)
				heapq.heappush(temp, -arr[j])
				reserve = []
				alpha_old = alpha_new
				if alpha_new == k:
					flag = True
				if freq[freq[-temp[0]]] != 0:
					beautiful = beautiful + 1
			elif arr[j] < -temp[0]:
				reserve.append(-heapq.heapreplace(temp, -arr[j]))
				if freq[freq[-temp[0]]] != 0:
					beautiful = beautiful + 1
			else:
				reserve.append(arr[j])
				if freq[freq[-temp[0]]] != 0:
					beautiful = beautiful + 1
	print(beautiful)


import math
from bisect import insort
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		counter = [0] * 2001
		current = []
		length = 0
		for j in range(i, n):
			insort(current, a[j])
			length += 1
			counter[a[j]] += 1
			repeat = (k + length - 1) // length
			index = k // repeat
			if k % repeat == 0:
				index -= 1
			if counter[counter[current[index]]]:
				ans += 1
	print(ans)


from bisect import insort
from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		count = [0] * 2001
		temp = []
		for j in range(i, n):
			count[array[j]] += 1
			insort(temp, array[j])
			m = ceil(k / (j - i + 1))
			t = ceil(k / m)
			x = temp[t - 1]
			f = count[x]
			if count[f]:
				ans += 1
	print(ans)


from math import ceil
from bisect import insort
for z in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	i = 0
	c = 0
	while i < n - 1:
		h = []
		cl = [0] * 2001
		j = 0
		while i + j < n:
			cl[a[i + j]] += 1
			insort(h, a[i + j])
			m = ceil(k / (j + 1))
			p = ceil(k / m)
			x = h[p - 1]
			f = cl[x]
			if cl[f]:
				c += 1
			j += 1
		i += 1
	print(c)


from collections import Counter
from math import ceil
test = int(input())
for _ in range(test):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	total = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			subarray = a[i:j]
			length = j - i
			c = Counter(subarray)
			m = k // length if k % length == 0 else k // length + 1
			kth = sorted(subarray)[ceil(k / m) - 1]
			F = c[kth]
			if F in c:
				total += 1
	print(total)


import bisect
import math
from sys import stdin
t = int(stdin.readline())
for x in range(t):
	(n, k) = list(map(int, stdin.readline().split()))
	a = list(map(int, stdin.readline().rstrip().split()))
	maxi = max(a)
	count = 0
	g = []
	cc = 0
	counting = 0
	for i in range(n):
		for j in range(n):
			p = math.ceil(k / (j - i + 1))
			index = math.ceil(k / p)
			g.append(index)
			cc = 1
		if cc == 1:
			break
	for i in range(n):
		s = []
		d = [0] * (maxi + 2)
		counting = 0
		for j in range(i, n):
			bisect.insort(s, a[j])
			d[a[j]] += 1
			l = i + 1
			r = j + 1
			index = g[counting]
			myele = s[index - 1]
			f = d[myele]
			if d[f] > 0:
				count += 1
			counting += 1
	print(count)


import math
from bisect import insort
t = int(input())
for i in range(t):
	ans = 0
	(n, k) = map(int, input().split())
	items = list(map(int, input().split()))
	j = 0
	m = 0
	e = []
	for s in range(2000):
		e.append(int((k - 1) / math.ceil(k / (s + 1))))
	for a in range(n):
		j = a + 1
		sub = []
		c = 0
		count = [0] * 2000
		while j <= n:
			count[items[c + a] - 1] += 1
			insort(sub, items[c + a])
			if count[count[sub[e[j - a - 1]] - 1] - 1] > 0:
				ans += 1
			j += 1
			c += 1
	print(ans)


import math
import bisect
tc = int(input())
for x in range(0, tc):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	array = [int(i) for i in input().split()]
	ans = 0
	indexdic = {1: 0}
	for i in range(2, n + 1):
		m = math.ceil(k / i)
		indexdic[i] = math.floor((k - 1) / m)
	for i in range(0, n):
		sortedlist = [array[i]]
		freq = {array[i]: 1}
		num = sortedlist[0]
		c = freq[num]
		if c in freq:
			ans += 1
		for j in range(i + 1, n):
			bisect.insort(sortedlist, array[j])
			if array[j] in freq:
				freq[array[j]] += 1
			else:
				freq[array[j]] = 1
			index = indexdic[len(sortedlist)]
			num = sortedlist[index]
			c = freq[num]
			if c in freq:
				ans += 1
	print(ans)


from bisect import insort, bisect_left
from math import ceil
for _ in range(int(input().strip())):
	(n, k) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	indices = [ceil(k / ceil(k / l)) - 1 for l in range(1, 2001)]
	c = 0
	for i in range(n):
		sub = []
		freq = [0] * 2001
		for j in range(i, n):
			insort(sub, arr[j])
			l = len(sub)
			freq[arr[j]] += 1
			if sub[0] > l:
				continue
			x = sub[indices[l - 1]]
			if freq[freq[x]] != 0:
				c += 1
	print(c)


import bisect
import math
t = int(input())
while t > 0:
	t = t - 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = input().split()
	arr_new = []
	mth = []
	for i in range(n):
		arr_new.append(int(arr[i]))
		leng = i + 1
		cur = int(math.ceil(k / math.ceil(k / leng)) - 1)
		mth.append(cur)
	total_count = 0
	for i in range(n):
		arr_sorted = list()
		arr_count = dict()
		for j in range(i, n):
			cur = arr_new[j]
			if arr_count.get(cur, -1) == -1:
				arr_count[cur] = 1
			else:
				arr_count[cur] += 1
			bisect.insort(arr_sorted, cur)
			leng = j - i
			cur_count = arr_count[arr_sorted[mth[leng]]]
			if arr_count.get(cur_count, -1) != -1:
				total_count += 1
	print(total_count)


import bisect
import sys
from sys import stdin, stdout
test = int(sys.stdin.readline())
while test > 0:
	test = test - 1
	nk = [int(x) for x in sys.stdin.readline().split()]
	n = nk[0]
	k = nk[1]
	arr = [int(x) for x in sys.stdin.readline().split()]
	arr.insert(0, 0)
	c = 0
	pre = [0 for k in range(2001)]
	for i in range(1, 2001):
		m = int(k / i) + 1
		if k % i == 0:
			m = m - 1
		x = int(k / m) + 1
		if k % m == 0:
			x = x - 1
		pre[i] = x
	for i in range(1, n + 1):
		brr = [0 for k in range(2001)]
		lis = []
		for j in range(i, n + 1):
			brr[arr[j]] = brr[arr[j]] + 1
			bisect.insort(lis, arr[j])
			size = j - i + 1
			xt = pre[size]
			y = lis[xt - 1]
			f = brr[y]
			if brr[f] > 0:
				c = c + 1
	print(c)


def div(a, b):
	if a % b == 0:
		return a // b
	return a // b + 1
t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	ans = 0
	m = []
	for i in range(n):
		m.append(div(k, div(k, i + 1)) - 1)
	for i in range(n):
		if a[i] == 1:
			ans += 1
		inarr = [0] * 2001
		inarr[a[i]] = 1
		arr = []
		p = a[i]
		no = 1
		for j in range(i + 1, n):
			inarr[a[j]] += 1
			c = m[j - i] - m[j - i - 1]
			if a[j] < p:
				c -= 1
			if c == -1:
				no -= 1
				if no == 0:
					l = p - 1
					while inarr[l] == 0:
						l -= 1
					p = l
					no = inarr[p]
			else:
				while c:
					c -= 1
					no += 1
					if no > inarr[p]:
						l = p + 1
						while inarr[l] == 0:
							l += 1
						p = l
						no = 1
			if inarr[inarr[p]] != 0:
				ans += 1
	print(ans)


import bisect as b
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		x = [0]
		d = dict()
		for j in range(i, n):
			b.insort(x, a[j])
			y = k / (len(x) - 1)
			if d.get(a[j], -1) == -1:
				d[a[j]] = 1
			else:
				d[a[j]] += 1
			if int(y) != y:
				y = int(y) + 1
			y = int(y)
			z = k / y
			if int(z) != z:
				z = int(z) + 1
			z = int(z)
			q = d[x[z]]
			if d.get(q, -1) != -1:
				c += 1
	print(c)


from bisect import insort
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	items = list(map(int, input().split()))
	ans = 0
	e = [0 for i in range(n)]
	for i in range(n):
		t = (k - 1) // (i + 1)
		e[i] = (k + t) // (t + 1) - 1
	for a in range(n):
		j = a + 1
		sub = []
		c = 0
		count = [0] * 2000
		while j <= n:
			count[items[c + a] - 1] += 1
			insort(sub, items[c + a])
			if count[count[sub[e[j - a - 1]] - 1] - 1] > 0:
				ans += 1
			j += 1
			c += 1
	print(ans)


import bisect
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		temp = []
		occ = [0] * 2001
		for j in range(i, n):
			bisect.insort(temp, a[j])
			occ[a[j]] += 1
			m = (k + j - i) // (j - i + 1)
			ele = temp[(k - 1) // m]
			if occ[occ[ele]]:
				ans += 1
	print(ans)


import bisect
t = int(input())
for y in range(t):
	(n, k) = (int(x) for x in input().split())
	places = []
	for l in range(1, n + 1):
		m = (k - 1) // l + 1
		shoot = m * l - k
		place = shoot // m + 1
		places.append(place)
	A = [int(x) for x in input().split()]
	assert len(A) == n
	ans = 0
	for l in range(n):
		elements = [0] * 2001
		S = []
		for r in range(l, n):
			try:
				elements[A[r]] += 1
			except:
				elements[A[r]] = 1
			bisect.insort(S, A[r])
			x = S[-places[r - l]]
			f = elements[x]
			try:
				if elements[f] > 0:
					ans += 1
			except:
				pass
	print(ans)


from math import ceil
from bisect import insort
t = int(input())
for k in range(t):
	(a, b) = map(int, input().split())
	li = list(map(int, input().split()))
	c = 0
	i = 0
	p = []
	while i < a:
		p.append(ceil(b / ceil(b / (i + 1))))
		i += 1
	i = 0
	while i < a - 1:
		h = []
		co = [0] * 2001
		j = 0
		while i + j < a:
			co[li[j + i]] += 1
			insort(h, li[i + j])
			x = h[p[j] - 1]
			f = co[x]
			if co[f]:
				c += 1
			j += 1
		i += 1
	print(c)


import bisect
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = []
	ans = 0
	b = []
	for i in range(n):
		x = [0] * 2001
		b = []
		for j in range(i, n):
			bisect.insort(b, a[j])
			m = (k + (j - i + 1) - 1) // (j - i + 1)
			kth = b[(k - 1) // m]
			x[a[j]] += 1
			if x[x[kth]] > 0:
				ans += 1
	print(ans)


ttt = int(input())
import bisect, math
for _ in range(ttt):
	(n, k) = list(map(int, input().split()))
	it = list(map(int, input().split()))
	t = 0
	pos = []
	for j in range(1, n + 1):
		pos.append(math.ceil(k / math.ceil(k / j)) - 1)
	for i in range(n):
		sub = []
		cc = {}
		for j in range(i, n):
			cc[it[j]] = cc.get(it[j], 0) + 1
			bisect.insort_right(sub, it[j])
			x = sub[pos[j - i]]
			a = cc[x]
			if cc.get(a, 0) != 0:
				t += 1
	print(t)


import bisect
import math
loop = int(input())
for time in range(loop):
	length_counter = 1
	array = []
	position = []
	temp_input = input().split()
	temp_list = input().split()
	n = int(temp_input[0])
	k = int(temp_input[1])
	answer = 0
	for i in temp_list:
		array.append(int(i))
		temp = int(math.ceil(k / math.ceil(k / length_counter)) - 1)
		position.append(temp)
		length_counter += 1
	for i in range(0, n):
		sub_count = dict()
		sub_array = list()
		for j in range(i, n):
			temp = array[j]
			if sub_count.get(temp, -1) == -1:
				sub_count[temp] = 1
			else:
				sub_count[temp] += 1
			bisect.insort(sub_array, temp)
			x = sub_array[position[j - i]]
			f = sub_count[x]
			if sub_count.get(f, -1) != -1:
				answer += 1
	print(answer)


from math import ceil

def calculate(s, nth, dp):
	for i in range(2001):
		nth -= dp[s][i]
		if nth <= 0:
			return (i, nth * -1)
for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = 0
	dp = [[0 for i in range(2001)]]
	for ele in arr:
		dp.append(list(dp[-1]))
		dp[-1][ele] += 1
	index = -1
	extra = 0
	for s in range(1, n + 1):
		nth = ceil(k / ceil(k / s))
		(index, extra) = calculate(s, nth, dp)
		myli = list(dp[s])
		for p in range(n - s + 1):
			q = p + s - 1
			if p > 0:
				myli[arr[p - 1]] -= 1
				myli[arr[q]] += 1
				if arr[p - 1] <= index:
					extra -= 1
				if arr[q] <= index:
					extra += 1
				if extra == -1:
					index += 1
					while myli[index] == 0:
						index += 1
					extra = myli[index] - 1
				elif extra == myli[index]:
					index -= 1
					while myli[index] == 0:
						index -= 1
					extra = 0
			if myli[myli[index]] > 0:
				ans += 1
	print(ans)


import math
from heapq import heappush, heappop
import random

def get_input_line():
	return input()

def get_frequencies(array):
	frequencies = {}
	for number in array:
		frequencies[number] = frequencies.get(number, 0) + 1
	return frequencies

def solve_1(numbers, k):
	good_arrays = 0
	for i in range(len(numbers)):
		for j in range(i + 1, len(numbers) + 1):
			current_array = numbers[i:j]
			frequencies = get_frequencies(current_array)
			multiplier = math.ceil(k / len(current_array))
			items = sorted(list(frequencies.items()))
			prev_multiplied_value = 0
			(k_lowest_value, k_lowest_index, k_lowest_occurrence) = (None, None, None)
			for (x, item) in enumerate(items):
				current_multiplied_value = prev_multiplied_value + item[1] * multiplier
				if prev_multiplied_value < k <= current_multiplied_value:
					k_lowest_value = item[0]
					k_lowest_index = x
					k_lowest_occurrence = item[1]
					break
				prev_multiplied_value = current_multiplied_value
			if k_lowest_occurrence in frequencies:
				good_arrays += 1
	return good_arrays

def solve_2(numbers, k):
	good_arrays = 0
	for i in range(len(numbers)):
		numbers_frequencies = [0] * 2001
		for j in range(i, len(numbers)):
			numbers_frequencies[numbers[j]] += 1
			multiplier = math.ceil(k / (j - i + 1))
			new_k = math.ceil(k / multiplier)
			cumulative_value = 0
			for t in range(1, 2001):
				freq = numbers_frequencies[t]
				if not freq:
					continue
				cumulative_value += freq
				if cumulative_value >= new_k:
					if numbers_frequencies[freq] > 0:
						good_arrays += 1
					break
	return good_arrays

def get_min_greater_position(array, value):
	left = 0
	right = len(array) - 1
	while left < right:
		mid = (left + right) // 2
		if value < array[mid]:
			right = mid - 1
		elif value > array[mid]:
			left = mid + 1
		else:
			return mid
	if value < array[left]:
		return left
	return left + 1

def insert(array, value):
	if not array:
		array.append(value)
	else:
		position = get_min_greater_position(array, value)
		array = array[:position] + [value] + array[position:]
	return array

def solve_3(numbers, k):
	good_arrays = 0
	for i in range(len(numbers)):
		sorted_array = []
		unique_values = {}
		for j in range(i, len(numbers)):
			unique_values[numbers[j]] = 1 + unique_values.get(numbers[j], 0)
			sorted_array = insert(sorted_array, numbers[j])
			multiplier = math.ceil(k / (j - i + 1))
			new_k = int(math.ceil(k / multiplier))
			if unique_values[sorted_array[new_k - 1]] in unique_values:
				good_arrays += 1
	return good_arrays

def solve_4(numbers, k):
	good_arrays = 0
	new_ks = [0] * len(numbers)
	for i in range(len(numbers)):
		multiplier = math.ceil(k / (i + 1))
		new_ks[i] = int(math.ceil(k / multiplier))
	for i in range(len(numbers)):
		unique_values = {}
		items_in_heap = 0
		max_heap = []
		min_heap = []
		for j in range(i, len(numbers)):
			unique_values[numbers[j]] = 1 + unique_values.get(numbers[j], 0)
			heappush(max_heap, -numbers[j])
			items_in_heap += 1
			new_k = new_ks[j - i]
			while items_in_heap < new_k:
				heappush(max_heap, -heappop(min_heap))
				items_in_heap += 1
			while items_in_heap > new_k:
				heappush(min_heap, -heappop(max_heap))
				items_in_heap -= 1
			kth_largest = -max_heap[0]
			if unique_values[kth_largest] in unique_values:
				good_arrays += 1
	return good_arrays

def solve_5(numbers, k):
	good_arrays = 0
	new_ks = [0] * len(numbers)
	for i in range(len(numbers)):
		multiplier = math.ceil(k / (i + 1))
		new_ks[i] = int(math.ceil(k / multiplier))
	for i in range(len(numbers)):
		unique_values = {}
		items_in_heap = 0
		max_heap = []
		prev_removed = []
		for j in range(i, len(numbers)):
			unique_values[numbers[j]] = 1 + unique_values.get(numbers[j], 0)
			heappush(max_heap, -numbers[j])
			items_in_heap += 1
			new_k = new_ks[j - i]
			while items_in_heap < new_k:
				heappush(max_heap, prev_removed.pop())
				items_in_heap += 1
			while items_in_heap > new_k:
				prev_removed.append(heappop(max_heap))
				items_in_heap -= 1
			kth_largest = -max_heap[0]
			if unique_values[kth_largest] in unique_values:
				good_arrays += 1
	return good_arrays

def solve_6(numbers, k):
	good_arrays = 0
	new_ks2 = [0] * len(numbers)
	for i in range(len(numbers)):
		multiplier = math.ceil(k / (i + 1))
		new_ks2[i] = i + 2 - int(math.ceil(k / multiplier))
	for i in range(len(numbers)):
		unique_values = {}
		items_in_heap = 0
		min_heap = []
		for j in range(i, len(numbers)):
			unique_values[numbers[j]] = 1 + unique_values.get(numbers[j], 0)
			heappush(min_heap, numbers[j])
			items_in_heap += 1
			new_k = new_ks2[j - i]
			while items_in_heap > new_k:
				heappop(min_heap)
				items_in_heap -= 1
			kth_largest = min_heap[0]
			if unique_values[kth_largest] in unique_values:
				good_arrays += 1
	return good_arrays

def main():
	test_count = int(get_input_line())
	for i in range(test_count):
		(_, k) = map(int, get_input_line().split())
		numbers = list(map(int, get_input_line().split()))
		print(solve_4(numbers, k))
main()


from bisect import bisect_left

def BinarySearch(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return True
	else:
		return False
import math
for _ in range(int(input())):
	ans = 0
	(N, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	for i in range(N):
		for j in range(i, N):
			S = a[i:j + 1]
			S.sort()
			god = math.ceil(k / len(S))
			X = S[math.ceil(k / god) - 1]
			F = 0
			for z in S:
				if z == X:
					F += 1
			if BinarySearch(S, F):
				ans += 1
	print(ans)


import heapq
t = int(input())
for y in range(t):
	(n, k) = (int(x) for x in input().split())
	places = []
	for l in range(1, n + 1):
		m = (k - 1) // l + 1
		shoot = m * l - k
		place = shoot // m + 1
		places.append(place)
	A = [int(x) for x in input().split()]
	heaps = [[-x] for x in A]
	assert len(A) == n
	ans = A.count(1)
	for l in range(1, n):
		elements = [0] * 2001
		for e in A[:l + 1]:
			try:
				elements[e] += 1
			except:
				elements[e] = 1
		for s in range(0, n - l):
			heapq.heappush(heaps[s], -A[s + l])
			if places[l] > 2:
				reserve = []
				for i in range(places[l]):
					reserve.append(heapq.heappop(heaps[s]))
				for r in reserve:
					heapq.heappush(heaps[s], r)
				x = -reserve[-1]
			elif places[l] == 2:
				x = max(-heaps[s][1], heaps[s][2])
			else:
				x = -heaps[s][0]
			f = elements[x]
			try:
				if elements[f] > 0:
					ans += 1
			except:
				pass
			if s < n - l - 1:
				try:
					elements[A[s]] -= 1
					elements[A[s + l + 1]] += 1
				except:
					elements[A[s + l + 1]] = 1
	print(ans)


import math
import bisect

def make_subarrays(a, n, k):
	beautiful = 0
	for i in range(n):
		l = []
		f = [0] * 2001
		for j in range(i, n):
			cur = a[j]
			bisect.insort(l, cur)
			f[cur] += 1
			size = j - i + 1
			p = math.ceil(k / size)
			r = math.ceil(k / p)
			c = f[f[l[r - 1]]]
			if c > 0:
				beautiful += 1
	return beautiful
t = int(input())
while t:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	beautiful = make_subarrays(a, n, k)
	print(beautiful)
	t -= 1


from math import ceil
from collections import defaultdict
from bisect import bisect_left, bisect_right, insort
from sys import stdin

def solve():
	for _ in range(int(stdin.readline())):
		(N, K) = map(int, stdin.readline().split())
		A = [int(k) for k in stdin.readline().split()]
		mA = min(A)
		if mA > N:
			print(0)
			continue
		ls = len(set(A))
		if ls == 1:
			print(max(0, N - A[0] + 1))
			continue
		if ls == N:
			if mA == 1:
				idx = A.index(1)
				ans = 0
				for i in range(idx + 1):
					ans += N - idx
				print(ans)
			else:
				print(0)
			continue
		freq = defaultdict(list)
		for i in range(N):
			freq[A[i]].append(i)
		ans = len(freq[1])
		for i in range(N - 1):
			S = [A[i]]
			freq2 = defaultdict(int)
			freq2[S[0]] += 1
			for j in range(i + 1, N):
				aj = A[j]
				freq2[aj] += 1
				insort(S, aj)
				m = ceil(K / (j - i + 1))
				k = ceil(K / m) - 1
				x = S[k]
				prev = k
				f = freq2[x]
				cont = 1 if f in freq2 else 0
				if cont:
					ans += 1
		print(ans)
solve()


import sys
import bisect
t = int(sys.stdin.readline())
for it in range(t):
	(n, k) = [int(tmp) for tmp in sys.stdin.readline().split()]
	a = [int(tmp) for tmp in sys.stdin.readline().split()]
	bs = 0
	lmkm1ls = [-1] * (n + 1)
	ldkm1ls = [-1] * (n + 1)
	lrevxpc = [-1] * (n + 1)
	for l in range(n):
		s = []
		ls = 0
		lfs = [0] * 2001
		for er in a[l:n]:
			ls += 1
			bisect.insort(s, er)
			lfs[er] += 1
			if k <= ls:
				x = s[k - 1]
			else:
				if lmkm1ls[ls] == -1:
					lmkm1ls[ls] = (k - 1) % ls
					ldkm1ls[ls] = (k - 1) // ls
					lrevxpc[ls] = (ls - 1 - lmkm1ls[ls]) // (ldkm1ls[ls] + 1) + 1
				x = s[-lrevxpc[ls]]
			f = lfs[x]
			bs += lfs[f] != 0
	print(bs)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	from math import ceil
	l = [int(i) for i in input().split()]
	cnt = 0
	from collections import defaultdict
	from bisect import bisect_left as bl
	for i in range(n):
		curr = []
		d = defaultdict(int)
		for j in range(i, n):
			add = ceil(k / (j - i + 1))
			ind = bl(curr, l[j])
			curr.insert(ind, l[j])
			d[l[j]] += 1
			if k <= j - i + 1:
				x = curr[k - 1]
			else:
				x = curr[ceil(k / add) - 1]
			z = d[x]
			if d[z]:
				cnt += 1
	print(cnt)


def division(a, b):
	if a % b == 0:
		return a // b
	return a // b + 1
test = int(input())
for _ in range(test):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	res = 0
	p = []
	for i in range(n):
		p.append(division(k, division(k, i + 1)) - 1)
	for i in range(n):
		if a[i] == 1:
			res += 1
		inarr = [0] * 2001
		inarr[a[i]] = 1
		arr = []
		o = a[i]
		nop = 1
		for j in range(i + 1, n):
			inarr[a[j]] += 1
			c = p[j - i] - p[j - i - 1]
			if a[j] < o:
				c -= 1
			if c == -1:
				nop -= 1
				if nop == 0:
					q = o - 1
					while inarr[q] == 0:
						q -= 1
					o = q
					nop = inarr[o]
			else:
				while c:
					c -= 1
					nop += 1
					if nop > inarr[o]:
						q = o + 1
						while inarr[q] == 0:
							q += 1
						o = q
						nop = 1
			if inarr[inarr[o]] != 0:
				res += 1
	print(res)


def ceil(x, y):
	if x % y:
		return x // y + 1
	else:
		return x // y
MAX = 2001
t = int(input())
for t_i in range(t):
	(N, K) = map(int, input().split())
	Arr = list(map(int, input().split()))
	res = 0
	count_list = [None] * MAX
	for i in range(N):
		for value in range(MAX):
			count_list[value] = 0
		max_item = Arr[i]
		current_item = Arr[i]
		current_item_dis = 0
		for j in range(i, N):
			size = j - i + 1
			new_pos = ceil(K, ceil(K, size))
			new_item = Arr[j]
			count_list[new_item] += 1
			if new_item > max_item:
				max_item = new_item
			if size == new_pos:
				current_item = max_item
				current_item_dis = count_list[max_item] - 1
			elif new_item < current_item:
				if current_item_dis:
					current_item_dis -= 1
				else:
					current_item -= 1
					while not count_list[current_item]:
						current_item -= 1
					current_item_dis = count_list[current_item] - 1
			if count_list[count_list[current_item]]:
				res += 1
	print(res)


import math
import bisect
t = int(input())
for i in range(t):
	li = input().split()
	n = int(li[0])
	k = int(li[1])
	lj = input().split()
	l = []
	poi = 1
	pos = []
	for j in lj:
		l.append(int(j))
		pos.append(int(math.ceil(k / math.ceil(k / poi)) - 1))
		poi += 1
	ans = 0
	for j in range(n):
		sub = list()
		count = dict()
		for m in range(j, n):
			temp = l[m]
			bisect.insort(sub, temp)
			if count.get(temp, -1) == -1:
				count[temp] = 1
			else:
				count[temp] += 1
			x = sub[pos[m - j]]
			f = count[x]
			if count.get(f, -1) != -1:
				ans += 1
	print(ans)


from math import ceil
from bisect import insort
from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	d = defaultdict(int)
	for i in range(n):
		d[i + 1] = ceil(k / ceil(k / (i + 1))) - 1
	for i in range(n):
		s = []
		t = defaultdict(int)
		for j in range(i, n):
			insort(s, a[j])
			t[a[j]] += 1
			if t[s[d[j - i + 1]]] in t:
				ans += 1
	print(ans)


import bisect
from math import ceil
for _ in range(int(input())):
	res = 0
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		c = [0] * 2001
		arr = []
		for j in range(i, n):
			bisect.insort(arr, a[j])
			c[a[j]] += 1
			x = j - i + 1
			s = ceil(k / x)
			s = (k - 1) // s
			ans = arr[s]
			if c[c[ans]] != 0:
				res += 1
	print(res)


import bisect
for t in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	c = 0
	pre = [0 for k in range(2001)]
	for i in range(1, 2001):
		m = int(k / i) + 1
		if k % i == 0:
			m = m - 1
		x = int(k / m) + 1
		if k % m == 0:
			x = x - 1
		pre[i] = x
	for i in range(1, n + 1):
		brr = [0 for k in range(2001)]
		lis = []
		for j in range(i, n + 1):
			brr[arr[j]] = brr[arr[j]] + 1
			bisect.insort(lis, arr[j])
			size = j - i + 1
			xt = pre[size]
			y = lis[xt - 1]
			f = brr[y]
			if brr[f] > 0:
				c = c + 1
	print(c)