U teoriji informacija, Hemingovo rastojanje (eng. Hamming distance) između dva stringa jednakih dužina je broj pozicija na kojima se odgovarajući simboli razlikuju. Drugim rečima, ovo rastojanje meri minimalni broj zamena potrebnih za transformaciju jednog stringa u drugi.

U zadatku ćemo posmatrati 32-bitne brojeve, gde se Hemingovo rastojanje ham(a, b) računa kao broj bitova na kojima se brojevi a i b razlikuju. Na primer, Hemingovo rastojanje za brojeve 93 = 00...001011101 i 75 = 00...001001011 je 3, pošto se brojevi razlikuju na drugom, trećem i petom bitu s desna.

Dat je niz celih brojeva a dužine n. Odrediti zbir Hemingovih rastojanja svih parova elemenata niza, odnosno

∑_{i < j} ham(a[i], a[j]).

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu se nalazi prirodan broj n (1 < n < 100.000). U sledećih n redova se nalazi po jedan broj i oni predstavljaju niz a (0 < a[i] < 2 ³¹ - 1).

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu ispisati sumu Hemingovih rastojanja svaka dva broja u nizu.

Primer:

4
1
9
4
10

14

Objašnjenje.

Hemingova rastojanja za svaki par brojeva iz niza su jednaka ham(1, 9) = 1, ham(1, 4) = 2, ham(1, 10) = 3, ham(9, 4) = 3, ham(9, 10) = 2 i ham(4, 10) = 3. Suma svih rastojanja je upravo 14.

Primer:

7
128
7
0
99
18
10
1984

84

Napomena.

U 40% test primera, broj n će biti manji od 3.000.