题目描述

我们称一个序列的多样性为这个序列中总共出现了多少种不同的数。称一个序列的总多样性为其所有连续子序列的多样性总和。

$Zoran$ 有一个序列，他要对你进行 $Q$ 次独立的询问，在第 $i$ 次询问中，他想知道对序列的第 $l_i$ 到第 $r_i$ 项构成的连续子序列经过重排后，能达到的总多样性的最小值是多少。

输入格式
第一行输入两个正整数 $N, Q$ 表示序列的长度和询问次数。
接下来一行 $N$ 个数 $a_1, a_2, \ldots, a_N$，表示这个序列。
接下来 $Q$ 行，每行两个整数 $l_i, r_i$，表示一个询问。

输出格式
输出 $Q$ 行，第 $i$ 行输出对于第 $i$ 个询问的回答。

样例 1
输入

3 1
1 2 3
1 3

输出

10

解释：以任意顺序，每个连续子序列的多样性都等于它元素的个数。因此，对于询问的答案是 $1+1+1+2+2+3=10$。

样例 2
输入

4 2
1 1 1 1
1 2
2 4

输出

3
6

解释：以任意顺序，每个连续子序列的多样性都等于 $1$。因此，对于每个询问，答案都是给定连续子序列的连续子序列数。

样例 3
输入

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

输出

16
8
4

解释：对于第一个询问，一个最优顺序是 $(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$。

数据范围与提示