Preparing NOJ

An array of positive integers *a*_{1}, *a*_{2}, ..., *a*_{n} is given. Let us consider its arbitrary subarray *a*_{l}, *a*_{l + 1}..., *a*_{r}, where 1 ≤ *l* ≤ *r* ≤ *n*. For every positive integer *s* denote by *K*_{s} the number of occurrences of *s* into the subarray. We call the power of the subarray the sum of products *K*_{s}·*K*_{s}·*s* for every positive integer *s*. The sum contains only finite number of nonzero summands as the number of different values in the array is indeed finite.

You should calculate the power of *t* given subarrays.

First line contains two integers *n* and *t* (1 ≤ *n*, *t* ≤ 200000) — the array length and the number of queries correspondingly.

Second line contains *n* positive integers *a*_{i} (1 ≤ *a*_{i} ≤ 10^{6}) — the elements of the array.

Next *t* lines contain two positive integers *l*, *r* (1 ≤ *l* ≤ *r* ≤ *n*) each — the indices of the left and the right ends of the corresponding subarray.

Output *t* lines, the *i*-th line of the output should contain single positive integer — the power of the *i*-th query subarray.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preferred to use cout stream (also you may use %I64d).

3 2

1 2 1

1 2

1 3

3

6

8 3

1 1 2 2 1 3 1 1

2 7

1 6

2 7

20

20

20

Consider the following array (see the second sample) and its [2, 7] subarray (elements of the subarray are colored):

Info

Provider CodeForces

Origin Yandex.Algorithm 2011Round 2

Code CF86D

Tags

data structuresimplementationmathtwo pointers

Submitted 5

Passed 3

AC Rate 60%

Date 03/03/2019 20:29:21

Related