Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: giminaiciai.in

Rezultatų failas: giminaiciai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Giminaičiai

Tolimoje Briedžių tako galaktikoje yra nedidelė linksmažmogių apgyvendinta planeta. Linksmažmogiai yra tokie nuoširdūs ir draugiški su visais, jog iš jų sąmonės net išnyko giminaičio sąvoka. Todėl nieko nuostabaus, jei kuris nors linksmažmogis nežino, kas yra jo brolis, sesuo, pusbrolis ar pusseserė. Tačiau planetos demografijos tyrėjams tai anaiptol nėra džiugi žinia, kadangi jiems ši informacija yra reikalinga.

Tyrėjai sunumeravo visus linksmažmogius skaičiais nuo 1 iki N ir nuskaitė kiekvieno linksmažmogio i DNR kodą sveikuoju skaičiumi D_i. Mokslininkai išsiaiškino, kad linksmažmogių giminystę galima nustatyti pagal dvejetainę jų DNR kodų išraišką. Jie nustatė tokius galimus giminystės ryšius:

  • Dvyniai – linksmažmogiai i ir j yra dvyniai, jeigu jų DNR kodai D_i ir D_j dvejetainėje formoje yra vienodi.
  • Brolis/sesuo – linksmažmogiai i ir j yra broliai arba seserys, jeigu jų DNR koduose D_i ir D_j dvejetainėje formoje skiriasi lygiai vienas bitas.
  • Pusbrolis/pusseserė – linksmažmogiai i ir j yra pusbroliai arba pusseserės, jeigu jų DNR kodai D_i ir D_j dvejetainėje formoje skiriasi lygiai dviejuose bituose.
  • Kitais atvejais linksmažmogiai nelaikomi giminaičiais.

Padėkite demografijos tyrėjams rasti, kiek planetoje yra giminaičių porų.

Pradiniai duomenys

Pirmoje eilutėje – skaičius N (2\\leqN<2^{16}). Antroje eilutėje – N tarpais atskirtų sveikųjų skaičių D_i (1\\leqD_i\\leq10^9).

Rezultatai

Išveskite giminaičių porų skaičių.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
4
28 22 18 6
 
4
 
8
1 1 9 1 1 3 3 3
 
28