序列区间段查询问题：给出一个长度为 $n$ 的序列 $a$ 。$q$ 次询问，每次给定 $l,r,k$，求有多少个数对 $(l',r')$ 满足 $l \leq l' \leq r' \leq r$，使得 $\operatorname{mex}(\{a_{l'},a_{l'+1},...,a_{r'}\})=k$。
输入格式
输入的第一行包含两个整数 $n,q$。
接下来一行，包含 $n$ 个数，表示序列 $a$ 。
接下来 $q$ 行，每行三个整数 $l,r,k$。
输出格式
对于每组询问，输出一行一个整数，表示答案。
样例数据
样例输入
10 10
0 0 4 1 1 3 0 4 6 1
2 2 1
4 10 2
1 4 0
4 8 0
4 4 1
1 6 0
5 8 0
2 10 3
3 9 6
1 4 0样例输出
1
10
3
7
0
10
4
0
0
3子任务
对于 $10\%$ 的数据，$n,q \leq 1\,000$。
对于 $100\%$ 的数据，$1 \leq n,q \leq 230\,000$，$0 \leq a_i, k \leq 10^9$。
注
- 赛时并未提供空间限制，
“请选手自行评估”QOJ 上设置为 1 GB。