You are given a sequence of N integer numbers A. Calculate the sum of A_{i} AND A_{j} for all the pairs (i, j) where i < j. 
The AND operation is the Bitwise AND operation, defined as in here. 

------ Input ------ 

The first line of input consists of the integer N. 

The second line contains N integer numbers - the sequence A.

------ Output ------ 

Output the answer to the problem on the first line of the output.

------ Scoring ------ 

Subtask 1 (13 points): N ≤ 1000, A_{i} ≤ 1. 

Subtask 2 (39 points): N ≤ 1000, A_{i} ≤ 10^{9}. 

Subtask 3 (21 points): N ≤ 10^{5}, A_{i} ≤ 1. 

Subtask 4 (27 points): N ≤ 10^{5}, A_{i} ≤ 10^{6}. 

----- Sample Input 1 ------ 
5
1 2 3 4 5
----- Sample Output 1 ------ 
9

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Combinatorics

Mathematics


Solutions:
n = int(input())
l = list(map(int, input().split()))
res = 0
count = 0
for i in range(32):
	for j in range(n):
		if l[j] & 1:
			count += 1
		l[j] >>= 1
	res += count * (count - 1) // 2 * 2 ** i
	count = 0
print(res)


_ = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(32):
	ith_bit_count = 0
	for j in arr:
		if j & 1 << i:
			ith_bit_count += 1
	ans += ith_bit_count * (ith_bit_count - 1) // 2 * 2 ** i
print(ans)


n = int(input())
a = list(map(int, input().split()))
sum = 0
for i in range(32):
	num_bits = 0
	for j in range(n):
		if a[j] & 1 << i:
			num_bits += 1
	sum += (num_bits * (num_bits - 1) >> 1) * (1 << i)
print(sum)


n = int(input())
a = list(map(int, input().split()))
bits = [0] * 32
for i in range(32):
	for j in range(n):
		bits[i] += a[j] & 1
		a[j] >>= 1
ans = 0
for i in range(32):
	ans += bits[i] * (bits[i] - 1) // 2 * 2 ** i
print(ans)


def ans(arr, n):
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			ans += arr[i] & arr[j]
	print(ans)

def ans2(arr, n):
	bits = [0] * 31
	for i in arr:
		z = 1
		x = 0
		while z <= i:
			if z & i:
				bits[x] += 1
			x += 1
			z = z << 1
	ans = 0
	x = 1
	for i in range(31):
		if bits[i]:
			res = bits[i] * (bits[i] - 1) / 2
			res *= x
			ans += res
		x *= 2
	print(int(ans))
n = int(input())
arr = [int(i) for i in input().split()]
ans2(arr, n)


n = int(input())
num = list(map(int, input().split()))
ans = 0
for i in range(32):
	ct = 0
	for j in range(n):
		if 1 << i & num[j] == 1 << i:
			ct += 1
	ans += (1 << i) * (ct * (ct - 1)) // 2
print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = [0] * 30
for i in range(n):
	for j in range(30):
		if a[i] & 1 << j:
			ans[j] += 1
final = 0
for j in range(30):
	final += ans[j] * (ans[j] - 1) * (1 << j)
print(final // 2)


import itertools
import heapq
import collections
import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def inis():
	return input().split()

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	l = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			l.append(p)
	return l

def isPrime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False

def gcd(a):
	x = 0
	for p in a:
		x = math.gcd(x, p)
	return x
import math

def printDivisors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		i = i + 1
	ans.sort()
	return ans

def binaryToDecimal(n):
	return int(n, 2)

def holes(s):
	count = 0
	for i in s:
		if s == 'A' or s == 'D' or s == 'O' or (s == 'Q') or (s == 'P') or (s == 'R'):
			count += 1
		elif s == 'B':
			count += 2
	return count
n = inp()
a = inlt()
ans = 0
for i in range(40):
	ls = 1 << i
	temp = 0
	for j in range(n):
		if ls & a[j]:
			temp += 1
	ans += temp * (temp - 1) // 2 * ls
print(ans)


def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	(count, res) = ([0] * 32, 0)
	for x in A:
		p = 1
		for i in range(32):
			if x & 1 << i:
				res += p * count[i]
				count[i] += 1
			p *= 2
	print(res)
solve()


size = int(input())
arr = list(map(int, input().split()))
setbit = [0] * 32
for num in arr:
	i = 0
	while num > 0:
		if num & 1:
			setbit[i] += 1
		i += 1
		num = num // 2
ans = 0
for i in range(32):
	f = setbit[i]
	ans += f * (f - 1) * 2 ** i // 2
print(ans)


n = int(input())
arr = list(map(int, input().split()))[:n]
total = 0
for i in range(0, 30):
	y = 0
	for j in arr:
		if j & 2 ** i:
			y += 1
	total += y * (y - 1) // 2 * 2 ** i
print(total)


n = int(input())
arr = list(map(int, input().split(' ')))
ans = 0
for i in range(0, 32):
	c = 0
	for a in arr:
		if a & 1 << i:
			c += 1
	x = c * (c - 1) // 2
	ans += x * (1 << i)
print(ans)


from math import log
import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
N = int(input(''))
l = list(map(int, input('').split()))
bits = {}
sum = 0
for i in range(N):
	elem = l[i]
	if elem == 0:
		continue
	power = int(log(elem, 2))
	while power >= 0:
		if elem >= 2 ** power:
			if power + 1 not in bits:
				bits[power + 1] = 1
			else:
				bits[power + 1] += 1
			elem -= 2 ** power
		power -= 1
for bit in bits.keys():
	sum += 2 ** (bit - 1) * ncr(bits[bit], 2)
print(sum)


def pairAndSum(arr, n):
	ans = 0
	for i in range(0, 32):
		k = 0
		for j in range(0, n):
			if arr[j] & 1 << i:
				k = k + 1
		ans = ans + (1 << i) * (k * (k - 1) // 2)
	return ans
n = int(input())
arr = list(map(int, input().split()))
print(pairAndSum(arr, n))


def answer():
	bit = [0] * 30
	for x in a:
		for i in range(30):
			if x >> i & 1:
				bit[i] += 1
	ans = 0
	for i in range(len(bit)):
		ans += bit[i] * (bit[i] - 1) // 2 * (1 << i)
	return ans
n = int(input())
a = list(map(int, input().split()))
print(answer())


from collections import Counter
import string
import bisect
import math
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
testcases = 1
for _ in range(testcases):
	n = vary(1)
	num = array_int()
	ans = 0
	for i in range(32):
		ct = 0
		for j in range(n):
			if 1 << i & num[j] == 1 << i:
				ct += 1
		ans += (1 << i) * (ct * (ct - 1)) // 2
	print(ans)


def optimal(n, li):
	dt = dict()
	for val in li:
		binary = bin(val)[2:][::-1]
		for (pos, bit) in enumerate(binary):
			if bit == '1':
				dt[pos] = dt.get(pos, 0) + 1
	sm = 0
	for (pos, pwr) in dt.items():
		sm += pwr * (pwr - 1) // 2 * pow(2, pos)
	return sm
n = int(input())
li = list(map(int, input().split()))
print(optimal(n, li))


n = int(input())
lst = list(map(int, input().split()))
bit = [0] * 30
ans = 0
for i in range(30):
	count = 0
	for x in lst:
		if x & 1 << i:
			count += 1
	ans += count * (count - 1) // 2 * (1 << i)
print(ans)


import numpy as np
import sys
input = sys.stdin.readline
n = int(input())
a = np.array(list(map(int, input().split())))
s = 0
for i in range(32):
	k = 0
	for j in range(n):
		if a[j] & 1 << i:
			k += 1
	s += (1 << i) * (k * (k - 1) // 2)
print(s)


N = int(input())
arr = [int(i) for i in input().split()]
total = 0
frequency = [0 for i in range(30)]
for i in arr:
	for j in range(0, len(bin(i)[2:])):
		if i & 1 << j:
			frequency[j] += 1
for i in range(30):
	total += frequency[i] * (frequency[i] - 1) // 2 * 2 ** i
print(total)


n = int(input())
li = [int(x) for x in input().split()]
ans = 0
for i in range(30):
	c = 0
	for x in li:
		if x & 2 ** i:
			c += 1
	ans += 2 ** i * (c * (c - 1) // 2)
print(ans)


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
for i in range(32):
	k = 1 << i
	sum = 0
	for j in range(n):
		if k & arr[j]:
			sum += 1
	count += k * (sum * (sum - 1) // 2)
print(count)


n = int(input())
l = list(map(int, input().split()))
x = 0
for i in range(30):
	y = 0
	for j in l:
		if j & 2 ** i:
			y += 1
	x += y * (y - 1) // 2 * 2 ** i
print(x)


n = int(input())
a = [int(x) for x in input().split()]
sum = 0
for i in range(32):
	count = 0
	k = 1 << i
	for j in range(n):
		if k & a[j]:
			count += 1
	sum += k * (count * (count - 1) // 2)
print(sum)


N = int(input())
A = list(map(int, input().split()))
ans = 0
for b in range(31):
	c = 0
	for i in range(0, N):
		if A[i] & 1 << b:
			c += 1
	ans += (1 << b) * (c * (c - 1)) // 2
print(ans)


n = int(input())
a = [int(j) for j in input().split()]
ans = 0
for i in range(32):
	cur = 0
	for j in a:
		if j & 1 << i:
			cur += 1
	ans += (cur - 1) * cur // 2 * (1 << i)
print(ans)


n = int(input())
li = list(map(int, input().split()))
ki = [0] * 32
for i in range(n):
	s = str(bin(li[i])[2:])
	for j in range(len(s)):
		ki[32 - j - 1] = ki[32 - j - 1] + int(s[len(s) - j - 1])
c = 0
for i in range(32):
	a = ki[i] * (ki[i] - 1) // 2
	c = c + 2 ** (31 - i) * a
print(c)


n = int(input())
N = tuple(filter(lambda a: a != 0, list(map(int, input().split()))))
ans = 0
for i in range(32):
	c = 0
	for j in N:
		if j & 1 << i:
			c += 1
	ans += c * (c - 1) // 2 * (1 << i)
print(ans)


n = int(input())
p = 1
ar = list(map(int, input().split()))
ctr = 0
for i in range(31):
	x = 0
	for j in range(n):
		if ar[j] % 2 == 1:
			x += 1
		ar[j] = ar[j] // 2
	if (x - 1) % 2 == 0:
		ctr += x * ((x - 1) // 2) * p
	else:
		ctr += (x - 1) * (x // 2) * p
	p *= 2
print(ctr)


n = int(input())
a = list(map(int, input().split()))
bits = [0] * 31
for x in a:
	for b in range(31):
		if x & 1 << b > 0:
			bits[b] += 1
ans = 0
for b in range(31):
	ans += (bits[b] * (bits[b] - 1) >> 1) * (1 << b)
print(ans)


n = int(input())
arr = [int(x) for x in input().split()]
ans = 0
for i in range(32):
	cnt = 0
	for ele in arr:
		if ele & 1 << i:
			cnt = cnt + 1
	cnt = cnt * (cnt - 1) // 2
	ans += cnt * (1 << i)
print(ans)


n = int(input())
arr = list(map(int, input().split()))
s = 0
size = len(bin(max(arr))[2:])
arr = [bin(i)[2:].zfill(size) for i in arr]
s = 0
for i in range(size):
	count = 0
	for j in range(n):
		if arr[j][i] == '1':
			count += 1
	s += count * (count - 1) // 2 * 2 ** (size - i - 1)
print(s)


N = int(input())
A = list(map(int, input().split()))
onesCnt = [0] * 30
for i in range(N):
	val = A[i]
	bitPos = 0
	while val > 0:
		onesCnt[bitPos] += val % 2
		bitPos += 1
		val = int(val / 2)
ans = 0
for b in range(30):
	ans += int(2 ** b * onesCnt[b] * (onesCnt[b] - 1) / 2)
print(ans)


try:
	n = int(input())
	arr = list(map(int, input().split()))
	bins = [0] * 32
	for i in range(32):
		cnt = 0
		for j in range(len(arr)):
			if arr[j] & 1 << i:
				cnt += 1
		bins[i] = cnt
	ans = 0
	for i in range(len(bins)):
		cnt = bins[i]
		ans += cnt * (cnt - 1) // 2 * (1 << i)
	print(ans)
except:
	pass


import sys, threading
import math
import time
from os import path
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
import heapq

def lcm(a, b):
	return a * b // math.gcd(a, b)
si = lambda : str(input())
ii = lambda : int(input())
mii = lambda : map(int, input().split())
lmii = lambda : list(map(int, input().split()))
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')

def solve():
	n = ii()
	ans = 0
	a = lmii()
	vec = [0] * 31
	for i in range(n):
		for j in range(31):
			if a[i] & 1 << j:
				vec[j] += 1
	for j in range(31):
		cnt = vec[j] * (vec[j] - 1) // 2
		ans += cnt * (1 << j)
	print(ans)

def main():
	t = 1
	if path.exists('/Users/nitishkumar/Documents/Template_Codes/Python/CP/AtCoder/input.txt'):
		sys.stdin = open('/Users/nitishkumar/Documents/Template_Codes/Python/CP/AtCoder/input.txt', 'r')
		sys.stdout = open('/Users/nitishkumar/Documents/Template_Codes/Python/CP/AtCoder/output.txt', 'w')
		start_time = time.time()
		print('--- %s seconds ---' % (time.time() - start_time))
	sys.setrecursionlimit(10 ** 5)
	solve()
main()


n = int(input())
a = [int(x) for x in input().split()]
c = 0
f = 1
for i in range(32):
	d = 0
	for j in range(n):
		if a[j] & f << i:
			d += 1
	if d > 0:
		d = d * (d - 1) // 2
	c += d * (f << i)
print(c)


from math import *
from collections import *
from functools import *

def rvi():
	return [*map(int, input().split())]
n = int(input())
t = rvi()
b = [0] * 31
for x in t:
	for i in range(32):
		if x >> i & 1:
			b[i] += 1
print(sum([(1 << i) * ((max(0, j - 1) * max(0, j - 1) + max(0, j - 1)) // 2) for (i, j) in enumerate(b)]))


n = int(input())
x = [int(w) for w in input().split()]
y = [0] * 32
ans = 0
for i in range(32):
	c = 0
	for j in x:
		if j & 1 << i:
			c += 1
	ans += c * (c - 1) // 2 * 2 ** i
print(ans)


import math
n = int(input())
arr = list(map(int, input().split()))
tot = 0
for i in range(32):
	c = 0
	for j in arr:
		if (j >> i) % 2:
			c += 1
	if c <= 1:
		x = 0
	else:
		x = c * (c - 1) // 2
	sc = (1 << i) * x
	tot += sc
print(tot)


n = int(input())
a = list(map(int, input().split()))
s = 0
b = [0] * 32
for i in range(32):
	for j in range(n):
		b[i] += a[j] & 1
		a[j] >>= 1
for i in range(32):
	s += b[i] * (b[i] - 1) // 2 * 2 ** i
print(s)


t = int(input())
d1 = [int(a) for a in input().split()]
maxlen = 32
data = [bin(int(a))[2:].zfill(maxlen) for a in d1]
s = 0
for i in range(maxlen - 1, -1, -1):
	count = sum([1 for x in data if x[i] == '1'])
	n = 2 ** (maxlen - 1 - i) * (count * (count - 1) // 2)
	s += n
print(s)


n = int(input())
a = [int(_) for _ in input().split()]
b = [0] * 30
for x in a:
	for i in range(30):
		y = x & 1 << i
		if y != 0:
			b[i] += 1
s = 0
for i in range(30):
	s += b[i] * (b[i] - 1) * (1 << i)
print(s // 2)


N = int(input())
A = list(map(int, input().strip().split()))
result = 0
if N <= 1000:
	for i in range(N):
		for j in range(i + 1, N):
			result += A[i] & A[j]
else:
	data = [0] * 29
	for x in A:
		s = bin(x)
		n = len(s)
		for i in range(2, n):
			data[n - 1 - i] += int(s[i])
	for i in range(29):
		k = (data[i] - 1) * data[i] * 2 ** (i - 1)
		result += k
print(int(result))


n = int(input())
nums = [int(j) for j in input().split()]
encoding = [0 for _ in range(30)]
for num in nums:
	m = num
	for i in range(30):
		encoding[i] += m % 2
		m = m // 2
print(sum([2 ** i * encoding[i] * (encoding[i] - 1) // 2 for i in range(30)]))


import sys
from collections import Counter
import numpy as np
import math
test = False
N = int(input().strip())
A = list(map(int, input().strip().split(' ')))
if test:
	print('N, A = ', N, A)
grid = []
for i in range(N):
	b = '{0:b}'.format(A[i])
	lenb = len(b)
	b = '0' * (30 - lenb) + b
	if test:
		print(b)
	b = [int(x) for x in b]
	grid.append(b)
np_grid = np.array(grid)
if test:
	print('np_grid = ', np_grid)
grid_sum = sum(np_grid)
if test:
	print('grid_sum = ', grid_sum)
answer = 0
combos = []
vals = []
for i in range(30):
	combo = grid_sum[i] * (grid_sum[i] - 1) / 2
	combos.append(combo)
	val = 2 ** (29 - i)
	vals.append(val)
	if test:
		print(combo, val)
	answer += combo * val
print(int(answer))


def solve():
	n = int(input())
	li = [int(x) for x in input().split()]
	ans = 0
	for i in range(32):
		cnt = 0
		for ele in li:
			if ele & 1 << i:
				cnt += 1
		cnt = cnt * (cnt - 1) // 2
		ans += cnt * (1 << i)
	print(ans)
solve()


n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(0, 31):
	count = 0
	for j in range(n):
		if A[j] & 1 << i:
			count += 1
	ans += (1 << i) * (count * (count - 1)) // 2
print(ans)


def sol(A):
	ans = 0
	for i in range(0, 30 + 1):
		count = 0
		for j in A:
			if 1 << i & j != 0:
				count = count + 1
		ans += (1 << i) * (count * (count - 1)) // 2
	return ans
n = int(input())
A = list(map(int, input().split()))
print(sol(A))


n = int(input())
L = list(map(int, input().split()))
bits = [0] * 33
for i in range(n):
	for j in range(0, 33):
		z = 1 << j
		if L[i] & z:
			bits[j] += 1
ans = 0
for i in range(33):
	z = bits[i]
	if z:
		y = z * (z - 1) // 2
		x = 1 << i
		ans += x * y
print(ans)


n = int(input())
bit = list(map(int, input().split()))
mask = 1 << 30
ans = 0
for i in range(30, -1, -1):
	count = 0
	for andd in bit:
		if andd & mask != 0:
			count += 1
	ans += 2 ** i * (count * (count - 1) // 2)
	mask >>= 1
print(ans)


def modBy2Comb(li):
	l = len([i % 2 for i in li if i % 2 != 0])
	return l * (l - 1) // 2

def divideBy2(li):
	return [i // 2 for i in li if i // 2 != 0]

def solve(li):
	s = 0
	c = 1
	while li != []:
		s += modBy2Comb(li) * c
		li = divideBy2(li)
		c *= 2
	return s
N = input()
li = [int(i) for i in input().split(' ')]
print(solve(li))


n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(40):
	ls = 1 << i
	temp = 0
	for j in range(n):
		if ls & a[j]:
			temp += 1
	ans += temp * (temp - 1) // 2 * ls
print(ans)


import sys, math
n = int(input())
arr = [int(c) for c in input().split()]
counts = [0 for i in range(32)]
for i in arr:
	for j in range(32):
		if i & 1 << j:
			counts[j] += 1
ans = 0
for i in range(32):
	c = 0
	if counts[i]:
		n = counts[i]
		c = n * (n - 1) // 2
	ans += (1 << i) * c
print(ans)