题目背景

译自 CEOI2021 Day1 T1. Diversity。

题目描述

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

例如，序列 $(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$ 个询问的答案。

样例 #1

样例输入 #1

3 1
1 2 3
1 3

样例输出 #1

10

样例 #2

样例输入 #2

4 2
1 1 1 1
1 2
2 4

样例输出 #2

3
6

样例 #3

样例输入 #3

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

样例输出 #3

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$