题目背景

译自 CEOI2021 Day1 T1. Diversity。

原题时限 7s。由于洛谷时间以及测试点数量限制，这里只选取部分测试点并缩小时限。但保证在标程时限的 1.5 倍。

题目描述

定义一个序列的 多样性 为其不同的元素个数，一个序列的 总多样性 为其所有子区间的 多样性 的和。

例如，序列 $(1,1,2)$ 的 多样性 为 $2$ ，因为其有两种元素；它的 总多样性 为序列 $(1),(1),(2),(1,1),(1,2),(1,1,2)$ 的 多样性 之和，即 $1+1+1+1+2+2=8$。

给出长为 $N$ 的序列 $\{a _i\}$ 与 $Q$ 个互相独立的询问，每个询问给出 $[l,r]$。求将原序列 $[l,r]$ 内的数重排可以得到的该区间最小的 总多样性。

输入格式

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

第二行 $N$ 个整数，表示序列 $\{a_i\}$。

接下来 $Q$ 行，每行两个整数 $l_i,r_i$，表示第 $i$ 次询问的区间。

输出格式

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

3 1
1 2 3
1 3

10

4 2
1 1 1 1
1 2
2 4

3
6

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

16
8
4

提示

样例解释

对于第一组样例，无论怎样重排，询问区间的 总多样性 总是 $10$。

对于第二组样例，序列所有元素都为 $1$，故无需重排。区间 $[1,2]$ 的 总多样性 为 $3$，区间 $[2,4]$ 的 总多样性 为 $6$。

对于第三组样例，第一个询问可将序列重排为 $(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$。

子任务

所有测试点均满足 $1\leq N\leq 3\times 10^5$，$1\leq a_i\leq 3\times 10^5$，$1\leq Q\leq 5\times 10^4$。

各子任务的约束条件如下： | 子任务编号 | 分值 | 约束 | | :--------: | :--: | :----------------------------------------------------------: | | $1$ | $4$ | $1\leq N\leq 11$，$1\leq a_i\leq 3\times 10^5$，$Q=1$，$l_1=1$，$r_1=N$ | | $2$ | $10$ | $1\leq N\leq 3\times 10^5$，$1\leq a_i\leq 11$，$Q=1$，$l_1=1$，$r_1=N$ | | $3$ | $8$ | $1\leq N\leq 3\times 10^5$，$1\leq a_i\leq 23$，$Q=1$，$l_1=1$，$r_1=N$ | | $4$ | $16$ | $1\leq N\leq 3\times 10^5$，$1\leq a_i\leq 1000$，$Q=1$，$l_1=1$，$r_1=N$ | | $5$ | $26$ | $1\leq N\leq 3\times 10^5$，$1\leq a_i\leq 3\times 10^5$，$Q=1$，$l_1=1$，$r_1=N$ | | $6$ | $36$ | $1\leq N\leq 3\times 10^5$，$1\leq a_i\leq 3\times 10^5$，$1\leq Q\leq 5\times 10^4$ |