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⁵, the number of vegetables and number of questions.

Next line contains N integers 1 ≤ A_i ≤ 10⁹, 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