ADANUM - Ada and Numbering
Ada the Ladybug has sequence of different vegetables (for simplicity represented by numbers). She has a few interesting questions of following form: Choose some continuous subsequence of vegetables, then assign each kind of vegetable a distinct positive number. She wants to assign them in a way that the sum (of assigned numbers) over all vegetables will be as low as possible.
Input
The first line contains two integers 1 ≤ N, Q ≤ 2*105, the number of vegetables and number of questions.
Next line contains N integers 1 ≤ Ai ≤ 109, the kinds of vegetables.
Next Q lines contains two integers 1 ≤ I ≤ J ≤ N , the left and right indices of Ada's questions.
Output
For each question answer the minimal possible sum.
Example Input 1
10 5 1 1 3 2 4 1 3 1 1 4 1 3 1 10 5 10 3 5 5 8
Example Output 1
4 19 10 6 7
Example IO explanation
Assign 1 to 1 and 2 to 3
Assign 1 to 1, 2 to 4, 3 to 3 and 4 to 2 (swapping 4 and 3 would work too)
Assign 1 to 1 and 2 to 4 and 3 to 3
Assign 1 to 4, 2 to 3 and 3 to 4 (but any permutation would do)
Assign 1 to 1 and 2 to 4 and 3 to 3
Added by: | Morass |
Date: | 2017-02-12 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |