Problem
Esiste un array di numeri naturali a
1, a
2, ..., a
n. Considera alcuni dei suoi sottoarray a
l, a
l + 1, ..., a
r, dove 1 ≤ l ≤ r ≤ n, e per ogni numero naturale s denotiamo con K
s il numero di occorrenze del numero s in questo sottoarray. Chiamiamo cardinalità di un sottoarray la somma dei prodotti K
s·K
s·s su tutti gli interi distinti s. Poiché il numero di numeri diversi nell'array è finito, la somma contiene solo un numero finito di termini diversi da zero.
È necessario calcolare le cardinalità di ognuno dei t sottoarray dati.
Inserimento
La prima riga contiene due numeri interi n e t (1 ≤ n, t ≤ 200000) — rispettivamente la lunghezza dell'array e il numero di richieste.
La seconda riga contiene n numeri naturali ai (1 ≤ a
i ≤ 10
6) — elementi dell'array.
Le t righe successive contengono due numeri interi positivi l e r (1 ≤ l ≤ r ≤ n) — indici delle estremità sinistra e destra del sottoarray corrispondente.
Impressum
Stampa t righe, dove la i-esima riga contiene l'unico numero naturale — cardinalità dell'i-esimo sottoarray di query.
Esempi:
| Input |
Uscita |
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 |