题目描述

给定一个长度为 $N$ 的自然数序列 $a_1,a_2,\ldots,a_N$。

对于一个子区间 $[st,dr]$，考虑其中出现过的每种不同数值 $x$。若 $x$ 在该区间中的第一次出现位置为 $L_x$，最后一次出现位置为 $R_x$，则它对答案的贡献为：

若 $x$ 在区间中只出现一次，则贡献为 $0$。

对于每个询问区间 $[st,dr]$，请输出所有不同数值贡献之和：

输入格式

第一行包含两个整数 $N,M$，表示序列长度和询问数量。

第二行包含 $N$ 个整数，表示给定序列。

接下来 $M$ 行，每行包含两个整数 $st,dr$，表示一个询问区间。

输出格式

输出 $M$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

数据范围

• $1\le N,M\le 200000$；
• $1\le st\le dr\le N$；
• $1\le a_i\le N$；
• 约 $20\%$ 的测试满足 $N,M\le 1000$；
• 约 $25\%$ 的测试满足 $N,M\le 35000$，且序列中不同数值个数最多为 $100$；
• 约 $25\%$ 的测试满足 $N,M\le 70000$。

样例

输入

7 3
1 3 1 2 2 1 3
2 4
2 7
3 6

输出

0
9
4

样例解释

区间 $[2,4]$ 中每种数值都只出现一次，所以答案为 $0$。

区间 $[2,7]$ 中：

• $3$ 出现在位置 $2,7$，贡献 $5$；
• $1$ 出现在位置 $3,6$，贡献 $3$；
• $2$ 出现在位置 $4,5$，贡献 $1$。

总和为 $9$。

区间 $[3,6]$ 中，$1$ 的贡献为 $3$，$2$ 的贡献为 $1$，总和为 $4$。