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
```

```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