「CEOI2021」多样性
题目描述
题目译自 CEOI 2021 Day1 T1「Diversity」
我们称一个序列的多样性为这个序列中总共出现了多少种不同的数。称一个序列的总多样性为其所有连续子序列的多样性总和。
Zoran 有一个序列，他要对你进行 次独立的询问，在第 次询问中，他想知道对序列的第 到第 项构成的连续子序列经过重排后，能达到的总多样性的最小值是多少。
输入格式
第一行输入两个正整数 表示序列的长度和询问次数。
接下来一行 个数 ，表示这个序列。
接下来 行，每行两个整数 ，表示一个询问。
输出格式
输出 行，第 行输出对于第 个询问的回答。
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
数据范围与提示
| 子任务编号 | 附加限制 | 分值 |
|---|---|---|
| $1\le N\le 11,1\le a_i\le 3\times 10^5,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 11,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 23,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 10^3,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 3\times 10^5,Q=1,l_1=1,r_1=N$ | ||
| $1\le N\le 3\times 10^5,1\le a_i\le 3\times 10^5,1\le Q\le 5\times 10^4$ |