Power of the Array

You are given an array of $n$ natural numbers $a_1, a_2, a_3, \dots, a_n$.

The subarray from $l$ to $r$ is $a_l, a_{l+1}, \dots, a_r$.

Let $K_s$ be the number of times the natural number $s$ appears in the subarray.

The power of a subarray is the sum of $K_s \cdot K_s \cdot s$ over all natural numbers $s$.

Given the array and the ranges of several subarrays, write a program that computes the power of each subarray.

The first line contains the size of the array $n$ and the number of subarrays $t$ ($1 \le n, t \le 10^5$).

The second line contains $n$ natural numbers $a_i$ separated by spaces ($1 \le a_i \le 10^6$).

Each of the next $t$ lines contains two integers $l_i$ and $r_i$ that describe the range of a subarray ($1 \le l_i \le r_i \le n$).

For each subarray given in the input, print its power on its own line.