Problem Background

Translated from CEOI2021 Day1 T1. Diversity.

The original problem had a time limit of 7 seconds. Due to the time limit and the number of test cases on Luogu, only a selection of test cases is used here with a reduced time limit, but it is guaranteed to be within 1.5 times the time limit of the standard solution.

Problem Description

Define the diversity of a sequence as the number of distinct elements it contains, and the total diversity of a sequence as the sum of the diversities of all its subintervals.

For example, the diversity of the sequence $(1,1,2)$ is $2$ because it contains two distinct elements; its total diversity is the sum of the diversities of the subintervals $(1), (1), (2), (1,1), (1,2), (1,1,2)$, which is $1+1+1+1+2+2=8$.

Given a sequence of length $N$ $\{a_i\}$ and $Q$ independent queries, each query specifies an interval $[l, r]$. Determine the minimum total diversity of the interval $[l, r]$ after rearranging the numbers within that interval.

Input Format

The first line of input contains two integers $N$ and $Q$, representing the length of the sequence and the number of queries, respectively.

The second line contains $N$ integers, representing the sequence $\{a_i\}$.

The following $Q$ lines each contain two integers $l_i$ and $r_i$, representing the interval for the $i$-th query.

Output Format

The output should consist of $Q$ lines of integers, where the $i$-th line contains the answer to the $i$-th query.

Sample Input and Output

Input Sample #1

3 1
1 2 3
1 3

Output Sample #1

10

Input Sample #2

4 2
1 1 1 1
1 2
2 4

Output Sample #2

3
6

Input Sample #3

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

Output Sample #3

16
8
4

Notes/Hints

Sample Explanation

For the first sample, regardless of how the sequence is rearranged, the total diversity of the queried interval is always $10$.

For the second sample, since all elements of the sequence are $1$, 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, the first query can rearrange the sequence to $(1,2,2,3)$, whose total diversity is $1+1+1+1+2+1+2+2+2+3=16$; the second query can rearrange the sequence to $(1,1,2)$, whose total diversity is $1+1+1+1+2+2=8$; the third query can rearrange the sequence to $(1,3)$, whose total diversity is $1+1+2=4$.

Subtasks

All test cases 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:

见题面 Input 部分

见题面 Output 部分