小C的秘境探险

时间限制：3000MS 512MB

题目描述

小C来到了一片神秘秘境探险。秘境中有 $n$ 块区域，第 $i$ 块区域有一个非负能量值 $a_i$ ，$n$ 块区域构成了一个序列 $a_n$。并且小C发现了这个区域有个神奇的性质：对于处在 $[l,r]$ 范围内的区域，会产生价值为 $Mex(a_l, a_{l+1}, ..., a_r)$ 的宝藏。

小C有 $q$ 次机会进行探险，每次探险他会被传送到 $r$ 位置，并且他只能向着负方向移动（即向左），至多移动到 $l$ 位置。每次探索只能运送价值**大于等于 $x$**的宝藏回去，因此小C想知道：有多少个区间能产生大于等于 $x$ 价值的宝藏。形式化描述的说，有 $q$ 次询问，每次询问给出一个区间 $[l, r]$ 和一个整数 $x$。需要回答：在询问区间内，有多少个 $i$ 满足 $i \geq l$ 且 $Mex(a_i, a_{i+1}, ..., a_r) \geq x$。

其中 $Mex(a_1, a_2, ..., a_n)$ 表示未在该序列中出现的最小非负整数。例如：

• $Mex(1, 2, 3) = 0$（0 是第一个未出现的非负整数）；
• $Mex(0, 1, 3) = 2$（2 是第一个未出现的非负整数）。

输入描述

问题有多组数据，第一行一个整数 $T$ 表示询问组数。

对于每组数据：

第 $1$ 行两个整数 $n，q$ 分别表示 $a_n$ 的长度，询问组数。

第 $2$ 行 $n$ 个整数，分别表示 $a_1, a_2, ..., a_n$ 。

第 $3$ 行到第 $2 + q$ 行，每行三个整数 $l, r, x$，分别表示区间和询问的 $Mex$。

输出描述

对于每组数据：

对于每个询问输出一行 $q$ 个整数表示答案。注意每一行末不可以输出多余空格

输入样例

1
6 4
1 0 2 3 4 5
1 3 2
4 6 0
2 5 1
1 5 4

输出样例

1 3 1 1