U579283 WNY 的三元组

WNY 在研究数学的过程中发现了一个神秘~~数字~~三元组！

WNY 手上有一个长度为 $n$ 的数组 $a$（下标 $1 \sim n$）。\ 现在 WNY 出了 $q$ 道题目，每道题的题面只有 $2$ 个数 $l,r$，答案是闭区间 $[l,r]$ 内 WNY 三元组的个数。 :::info[WNY 三元组的定义]{open} 对于三元组 $(i, j, k)$，若满足： - $l \le i < j < k \le r$ - $a_i = a_j = a_k$ 则称该三元组为闭区间 $[l,r]$ 内的 WNY 三元组。 ::: WNY 想要用这些题考考 ZLX，但是他此时正忙着研究费马大定理，所以他把求解答案的工作交给了你。

输入有 $q + 2$ 行。 第 $1$ 行：$2$ 个数 $n,q$。\ 第 $2$ 行：$n$ 个数，第 $i$ 个数是 $a_i$。\ 接下来 $q$ 行，每行 $2$ 个数 $l,r$。

输出有 $q$ 行。 每行输出 $1$ 个数，表示对应的问题的答案。

### 样例解释（#1） 闭区间 $[1,10]$ 内的 WNY 三元组分别为：$(1,5,9),(4,6,8),(4,6,10),(4,8,10),(6,8,10)$，共 $5$ 个。 ### 数据范围 对于 $100\%$ 的数据： - 保证输入均为正整数。 - $1 \le n,q,a_i \le 10^5$。 - $1 \le l \le r \le n$。 ::cute-table{tuack} | **Subtask** | **测试点** | **总分值** | **每个测试点的分值** | **$n,q,a_i \le$** | **特殊性质** | | :-: | :-: | :-: | :-: | :-: | :-: | | **Subtask 0** | $11 \sim 12$ | $0$ | $0$ | / | 题目样例 | | **Subtask 1** | $1 \sim 4$ | $40$ | $10$ | $10^3$ | 无 | | **Subtask 2** | $6 \sim 10$ | $60$ | ^ | $10^5$ | ^ |