U121098 [FJOI2020]序列区间段查询问题

给出一个长度为 $n$ 的序列 $a$ ，对于每次查询 $l,r,k$ ，求有多少个数对 $(i,j)(l\leq i\leq j\leq r)$ 满足 $mex(\{a_i,a_{i+1},...,a_j\})=k$。 $mex(S)$ 表示集合 $S$ 中最小的未出现的自然数。

第 $1$ 行 $2$ 个数 $n,q$ ，分别表示序列 $a$ 的长度及询问的数量。 接下来 $1$ 行 $n$ 个数，表示序列 $a$ 。 接下来 $q$ 行，每行 $3$ 个数 $l,r,k$ ，意义如题目描述所示。

对于每次查询，输出 $1$ 行，包含 $1$ 个数，表示有多少个数对 $(i,j)(l\leq i\leq j\leq r)$ 满足 $mex(\{a_i,a_{i+1},...,a_j\})=k$ 。

对于 $100\%$ 的数据， $n,q\leq 230000$ 。