## 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*10 ^{5}**, the number of vegetables and number of questions.

Next line contains ** N ** integers **1 ≤ A _{i} ≤ 10^{9}**, 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 |