Zoran 是萨格勒布动物园的一名饲养员。他目前正在进行一项关于游客满意度与动物在动物园中展示方式之间关系的科学研究。

游客在整个动物园的游览过程可以看作是一个包含 $N$ 个栖息地的序列，每个栖息地都饲养着某种动物。第 $i$ 个栖息地最初饲养着物种 $a_i$ 的动物，游客需要按顺序观察这些栖息地。

Zoran 开始尝试改变动物展示的顺序。随后，他询问了游客在游览过程中的满意度。结果发现，当游客游览过程的“总多样性”尽可能小时，他们的满意度最高。

在此，一个栖息地序列的“多样性”定义为在该序列中可以观察到的不同动物物种的数量，而一个栖息地序列的“总多样性”定义为该序列所有连续子序列的多样性之和。

例如，序列 $(1, 1, 2)$ 的多样性为 2，因为该序列中有两种不同的动物物种。同时，该序列的总多样性为 8，因为其连续子序列 $(1), (1), (2), (1, 1), (1, 2)$ 和 $(1, 1, 2)$ 的多样性分别为 1, 1, 1, 1, 2 和 2。

Zoran 知道目前每个栖息地饲养的动物物种。在重新规划动物园之前，他希望你回答 $Q$ 个独立的询问。在第 $i$ 个询问中，他想知道通过重新排列这些栖息地中的动物，从第 $l_i$ 个栖息地到第 $r_i$ 个栖息地这一连续子序列所能达到的最小总多样性。

输入格式

第一行包含两个整数 $N$ 和 $Q$。

第二行包含 $N$ 个空格分隔的整数 $a_1, a_2, \dots, a_N$。其中第 $i$ 个整数表示第 $i$ 个栖息地最初饲养的动物物种。

接下来的 $Q$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le N$)，描述一个询问。

注意，所有询问都是相互独立的，即你应该在假设第 $i$ 个栖息地最初由物种 $a_i$ 占据的前提下回答它们。

输出格式

第 $i$ 行输出应包含一个整数，表示第 $i$ 个询问的答案。

子任务

样例

输入 1

3 1
1 2 3
1 3

输出 1

10

输入 2

4 2
1 1 1 1
1 2
2 4

输出 2

3
6

输入 3

5 3
1 2 1 3 2
2 5
1 3
3 4

输出 3

16
8
4

说明

第一个样例的说明：在任何排列中，每个连续子序列的多样性都等于其元素个数。因此，该询问的答案为 $1 + 1 + 1 + 2 + 2 + 3 = 10$。

第二个样例的说明：在任何排列中，每个连续子序列的多样性都等于 1。因此，对于每个询问，答案就是给定连续子序列所包含的连续子序列的数量。

第三个样例的说明：在第一个询问中，一种最优排列是 $(1, 2, 2, 3)$，其总多样性为 $1 + 1 + 1 + 1 + 2 + 1 + 2 + 2 + 2 + 3 = 16$。在第二个询问中，一种最优排列是 $(1, 1, 2)$，其总多样性为 $1 + 1 + 1 + 1 + 2 + 2 = 8$。在第三个询问中，一种最优排列是 $(1, 3)$，其总多样性为 $1 + 1 + 2 = 4$。