P8171 [CEOI 2021] Diversity

Translated from CEOI 2021 Day 1 Task 1. [Diversity](https://hsin.hr/ceoi/competition/ceoi2021_day1_tasks.pdf)。

Define the *diversity* of a sequence as the number of distinct elements in it. Define the *total diversity* of a sequence as the sum of the *diversities* of all its subarrays. For example, the *diversity* of the sequence $(1,1,2)$ is $2$ because it contains two different elements. Its *total diversity* is the sum of the *diversities* of the subarrays $(1),(1),(2),(1,1),(1,2),(1,1,2)$, i.e. $1+1+1+1+2+2=8$. You are given a sequence $\{a_i\}$ of length $N$ and $Q$ **independent** queries. Each query gives an interval $[l,r]$. For each query, find the minimum possible *total diversity* of the subarray $[l,r]$ after rearranging the numbers inside $[l,r]$.

The first line contains two integers $N$ and $Q$, representing the sequence length and the number of queries. The second line contains $N$ integers, representing the sequence $\{a_i\}$. The next $Q$ lines each contain two integers $l_i, r_i$, representing the interval of the $i$-th query.

Output $Q$ lines of integers. The integer on the $i$-th line is the answer to the $i$-th query.

#### Sample Explanation For the first sample, no matter how you rearrange it, the *total diversity* of the queried interval is always $10$. For the second sample, all elements of the sequence are $1$, so no rearrangement is needed. The *total diversity* of interval $[1,2]$ is $3$, and the *total diversity* of interval $[2,4]$ is $6$. For the third sample, for the first query you can rearrange the sequence to $(1,2,2,3)$, whose *total diversity* is $1+1+1+1+2+1+2+2+2+3=16$. For the second query you can rearrange it to $(1,1,2)$, whose *total diversity* is $1+1+1+1+2+2=8$. For the third query you can rearrange it to $(1,3)$, whose *total diversity* is $1+1+2=4$. #### Subtasks All testdata satisfy $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$. The constraints for each subtask are as follows: | Subtask ID | Points | Constraints | | :--------: | :----: | :------------------------------------------------------------------: | | $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$ | Translated by ChatGPT 5