배열의 힘

자연수 $n$개로 이루어진 배열 $a_1, a_2, a_3, \dots, a_n$이 있다.

$l$부터 $r$까지의 부분 배열은 $a_l, a_{l+1}, \dots, a_r$이다.

$K_s$는 부분 배열 안에 들어 있는 자연수 $s$의 개수이다.

부분 배열의 힘이란 모든 자연수 $s$에 대해 $K_s \cdot K_s \cdot s$를 모두 더한 값이다.

배열과 여러 부분 배열의 범위가 주어질 때, 각 부분 배열의 힘을 구하는 프로그램을 작성하시오.

첫째 줄에 배열의 크기 $n$과 부분 배열의 개수 $t$가 주어진다. ($1 \le n, t \le 10^5$)

둘째 줄에는 $n$개의 자연수 $a_i$가 공백으로 구분되어 주어진다. ($1 \le a_i \le 10^6$)

다음 $t$개의 줄에는 각 부분 배열의 범위를 나타내는 두 정수 $l_i$와 $r_i$가 주어진다. ($1 \le l_i \le r_i \le n$)

입력으로 주어지는 각 부분 배열의 힘을 한 줄에 하나씩 출력한다.