Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Sometimes, the stability of a stock market is at least as important as rapid price changes.

Let a stable block be a maximal consecutive block of days with same stock prices.

Moreover, let a stable block of order K be a stable block of length at least K.

For example, if stock prices for 7 consecutive days are: 20, 10, 10, 7, 7, 7, 10, then there are 4 stable blocks there: [20], [10, 10], [7, 7, 7] and [10]. Moreover, there are:

0 stable blocks of order 4 or higher
1 stable block of order 3: [7, 7, 7]
2 stable block of order 2: [10, 10], [7, 7, 7]
4 stable block of order 1: [20], [10, 10], [7, 7, 7] and [10]

Given historical prices of a stock across N days, the goal is to answer Q customers' questions.

The i-th question contains three integers L_{i}, R_{i} and K_{i}. It asks for the number of stable blocks of order K_{i}, if only the stock prices of the days in the range L_{i}, R_{i} are considered.

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

In the first line there is a single integer T, denoting the number of test cases to handle. After that the description of T test cases follow.

The first line of each test case contains two space-separated integers N and Q, denoting respectively, the number of days for which the stock prices are given, and the number of questions to answer.

The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N}, where A_{i} denotes the price of the stock on the i-th day. 

Q lines follow. In the i-th of them there are three space-separated integers L_{i}, R_{i} and K_{i} denoting the i-th query.

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

For each test case, print answers to all queries in the test case, one per line.

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

$1 ≤ T ≤ 5$ 
$1 ≤ N, Q ≤ 10^{5}$ 
$1 ≤ A_{i} ≤ 10^{6}$ 
$1 ≤ L_{i} ≤ R_{i} ≤ N$ 
$1 ≤ K_{i} ≤ R_{i} - L_{i} + 1$ 

------ Subtasks ------ 

Subtask #1: (10 points)

$1 ≤ N, Q ≤ 3000$ 

Subtask #2: (90 points)

$original constraints$

----- Sample Input 1 ------ 
2
8 5
20 10 10 10 7 7 7 10
2 6 2
3 6 2
3 6 3
3 8 3
3 8 1
3 2
27 27 27
1 3 1
2 2 1
----- Sample Output 1 ------ 
2
2
0
1
3
1
1
----- explanation 1 ------ 
There are two test cases to handle

Test case #1:
There are 8 days for which prices are given and 5 queries to handle.
The first query asks for the number of stable blocks of order 2 in range [2, 6], which corresponds to prices 10 10 10 7 7. The answer is 2 because there are two such blocks: 10 10 10 and 7 7.
The second query asks for the number of stable blocks of order 2 in range [3, 6], which corresponds to prices 10 10 7 7. The answer is 2 because there are two such blocks: 10 10 and 7 7.
The third query asks for the number of stable blocks of order 3 in range [3, 6], which corresponds to prices 10 10 7 7. The answer is 0 because there is no stable block of order 3 there (maximum order of a stable block is 2).
The fourth query asks for the number of stable blocks of order 3 in range [3, 8], which corresponds to prices 10 10 7 7 7 10. The answer is 1 because the only stable block of order 3 here is 7 7 7.
The fifth query asks for the number of stable blocks of order 1 in range [3, 8], which corresponds to prices 10 10 7 7 7 10. The answer is 3 because there are 3 stable blocks of order 1 there: 10 10, 7 7 7 and 10.

Test case #2:
There are 3 days for which prices are given and 2 queries to handle.
The first query asks for the number of stable blocks of order 1 in range [1, 3], which corresponds to prices 27 27 27. The answer is 1 because the only such block there is 27 27 27.
The second query asks for the number of stable blocks of order 1 in range [2, 2], which corresponds to a single price 27. The answer is 1 because the only such block there is 27.

Source: codechef | Difficulty: HARD
Tags: Square root algorithms

Sorting

Range queries

Segment trees revisited

Complete search

Data structures


Solutions:
from itertools import groupby
from operator import itemgetter
M = 2 ** 17
B = [0] * (M + 1)

def reset():
	global B
	B = [0] * (M + 1)

def update(idx, val):
	idx += 1
	while idx <= M:
		B[idx] += val
		idx += idx & -idx

def read(idx):
	r = 0
	idx += 1
	while idx > 0:
		r += B[idx]
		idx -= idx & -idx
	return r
for _ in range(int(input())):
	(N, Q) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	q = [[0, i] + [int(x) for x in input().split()] for i in range(Q)]
	groups = []
	i = 0
	for (g, (_, l)) in enumerate(groupby(a)):
		j = i
		gc = len(groups)
		for _ in l:
			a[j] = gc
			j += 1
		groups.append([1, gc, i, j - 1, j - i])
		i = j
	reset()
	q.extend(groups)
	q.sort(key=itemgetter(4, 0), reverse=True)
	for x in q:
		if x[0]:
			update(x[1], 1)
		else:
			(y, z) = (a[x[2] - 1] + 1, a[x[3] - 1] - 1)
			r = read(z) - read(y - 1) if z >= y else 0
			if z + 1 == y - 1:
				if x[3] - x[2] + 1 >= x[4]:
					r += 1
			else:
				if groups[y - 1][3] - x[2] + 1 + 1 >= x[4]:
					r += 1
				if x[3] - 1 - groups[z + 1][2] + 1 >= x[4]:
					r += 1
			x[-1] = r
	for x in sorted((x for x in q if x[0] == 0)):
		print(x[-1])