题目描述

题目译自 CEOI 2021 Day1 T1「Diversity」

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

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$ 个询问的回答。

3 1
1 2 3
1 3

10

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

4 2
1 1 1 1
1 2
2 4

3
6

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

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$。

数据范围与提示