序列区间段查询问题：给出一个长度为 $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$。

注

1. 赛时并未提供空间限制，“请选手自行评估” QOJ 上设置为 1 GB。