P8171 [CEOI 2021] Diversity

译自 CEOI2021 Day1 T1. [Diversity](https://hsin.hr/ceoi/competition/ceoi2021_day1_tasks.pdf)。

定义一个序列的 _多样性_ 为其不同的元素个数，一个序列的 _总多样性_ 为其所有子区间的 _多样性_ 的和。 例如，序列 $(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$ 个询问的答案。

#### 样例解释 对于第一组样例，无论怎样重排，询问区间的 _总多样性_ 总是 $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$ |