Problem
자연수 배열 a
1, a
2, ..., a
n이 있습니다. a
l, a
l + 1, ..., a
r, 여기서 1 ≤ l ≤ r ≤ n이고 각 자연수 s에 대해 K
s는 이 하위 배열에서 숫자 s의 발생 횟수를 나타냅니다. 하위 배열의 카디널리티를 모든 개별 정수 s에 대한 K
s·K
s·s의 합이라고 합시다. 배열에 있는 서로 다른 숫자의 수가 유한하기 때문에 합계에는 0이 아닌 항의 유한한 수만 포함됩니다.
주어진 t개의 하위 배열 각각의 카디널리티를 계산해야 합니다.
입력
첫 번째 줄에는 두 개의 정수 n과 t(1 ≤ n, t ≤ 200000)가 포함됩니다. 배열의 길이와 요청 수.
두 번째 줄은 n개의 자연수 ai (1 ≤ a
i ≤ 10
6) — 배열 요소.
다음 t 행에는 두 개의 양의 정수 l 및 r(1 ≤ l ≤ r ≤ n) — 해당 하위 배열의 왼쪽 및 오른쪽 끝의 인덱스.
출판물
t 라인을 인쇄합니다. 여기서 i번째 라인에는 자연수만 포함됩니다. — i번째 쿼리 하위 배열의 카디널리티.
예:
<몸>
| 입력 |
출력 |
3 2
1 2 1
1 2
1 3
| 3
6 |
8 3
1 1 2 2 1 3 1 1
27
16
27 |
20
20
20 |