Problem
Existe uma matriz de números naturais a
1, a
2, ..., a
n. Considere alguns de seus subarrays a
l, a
l + 1, ..., a
r, onde 1 ≤ l ≤ r ≤ n, e para cada número natural s denota por K
s o número de ocorrências do número s neste subarray. Vamos chamar a cardinalidade de um subarray de soma dos produtos K
s·K
s·s sobre todos os inteiros distintos s. Como o número de números diferentes na matriz é finito, a soma contém apenas um número finito de termos diferentes de zero.
É necessário calcular as cardinalidades de cada um dos t subarranjos dados.
Entrada
A primeira linha contém dois inteiros n e t (1 ≤ n, t ≤ 200000) — o comprimento do array e o número de requisições, respectivamente.
A segunda linha contém n números naturais ai (1 ≤ a
i ≤ 10
6) — elementos do array.
As próximas t linhas contêm dois inteiros positivos l e r (1 ≤ l ≤ r ≤ n) — índices das extremidades esquerda e direita do subarray correspondente.
Impressão
Imprima t linhas, onde a i-ésima linha contém o único número natural — cardinalidade do i-ésimo subarray de consulta.
Exemplos:
| Entrada |
Saída |
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 |