Background

Translated from CEOI 2021 Day 1 Task 1. Diversity。

Problem Description

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]$.

Input Format

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 Format

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

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

Hint

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