Problem
Il existe un tableau de nombres naturels a
1, a
2, ..., a
n. Considérons certains de ses sous-réseaux a
l, a
l + 1, ..., a
r, où 1 ≤ l ≤ r ≤ n, et pour chaque nombre naturel s on note K
s le nombre d'occurrences du nombre s dans ce sous-tableau. Appelons cardinalité d'un sous-tableau la somme des produits K
s·K
s·s sur tous les entiers distincts s. Étant donné que le nombre de nombres différents dans le tableau est fini, la somme ne contient qu'un nombre fini de termes non nuls.
Il est nécessaire de calculer les cardinalités de chacun des t sous-réseaux donnés.
Entrée
La première ligne contient deux entiers n et t (1 ≤ n, t ≤ 200000) — la longueur du tableau et le nombre de requêtes, respectivement.
La deuxième ligne contient n nombres naturels ai (1 ≤ a
i ≤ 10
6) — éléments de tableau.
Les t lignes suivantes contiennent deux entiers positifs l et r (1 ≤ l ≤ r ≤ n) — index des extrémités gauche et droite du sous-tableau correspondant.
Mentions légales
Imprimer t lignes, où la ième ligne contient le seul nombre naturel — cardinalité du ième sous-tableau de requête.
Exemples :
| Entrée |
Sortie |
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 |