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


hide comments
princemishra: 2021-12-06 07:16:40

mo + deque


Added by:Morass
Date:2017-02-12
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All