Amr loves Chemistry, and specially doing experiments. He is preparing for a new interesting experiment.

Amr has n different types of chemicals. Each chemical i has an initial volume of a_{i} liters. For this experiment, Amr has to mix all the chemicals together, but all the chemicals volumes must be equal first. So his task is to make all the chemicals volumes equal.

To do this, Amr can do two different kind of operations.   Choose some chemical i and double its current volume so the new volume will be 2a_{i}  Choose some chemical i and divide its volume by two (integer division) so the new volume will be $\lfloor \frac{a_{i}}{2} \rfloor$ 

Suppose that each chemical is contained in a vessel of infinite volume. Now Amr wonders what is the minimum number of operations required to make all the chemicals volumes equal?


-----Input-----

The first line contains one number n (1 ≤ n ≤ 10^5), the number of chemicals.

The second line contains n space separated integers a_{i} (1 ≤ a_{i} ≤ 10^5), representing the initial volume of the i-th chemical in liters.


-----Output-----

Output one integer the minimum number of operations required to make all the chemicals volumes equal.


-----Examples-----
Input
3
4 8 2

Output
2
Input
3
3 5 6

Output
5


-----Note-----

In the first sample test, the optimal solution is to divide the second chemical volume by two, and multiply the third chemical volume by two to make all the volumes equal 4.

In the second sample test, the optimal solution is to divide the first chemical volume by two, and divide the second and the third chemical volumes by two twice to make all the volumes equal 1.

Difficulty: HARD
Tags: Graph algorithms

Shortest paths

Greedy algorithms

Complete search

Mathematics
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
n = int(input())
s = list(map(int, input().split()))
l = [bin(i)[2:] for i in s]
length = [len(i) for i in l]
maxLen = max(length)
minLen = min(length)
loc = 0
flag = False
for j in range(minLen):
	for i in range(n):
		if l[i][j] != l[0][j]:
			flag = True
			break
	if flag:
		break
	loc += 1
result = sum(length) - loc * n
best = result
change = n * [-1]
for j in range(loc, maxLen):
	for i in range(n):
		if j >= length[i] or l[i][j] == '1':
			change[i] = 1
	result += sum(change)
	if result > best:
		break
	best = result
print(best)


from collections import Counter

def main():
	input()
	aa = list(map(int, input().split()))
	(le, l) = (max(aa).bit_length(), [])
	for (i, a) in enumerate(aa):
		j = le - a.bit_length()
		aa[i] = a << j
		l.append(j)
	(mi, ma) = (min(aa), max(aa))
	a = mask = (1 << le) - 1
	if mi == ma:
		while mi == mi & a:
			mask = a
			a &= a << 1
	else:
		while mi != ma or not mi & 1:
			mask &= mask << 1
			mi >>= 1
			ma >>= 1
	mask ^= (1 << le) - 1
	(le, cnt) = (mask.bit_length(), Counter())
	for (a, i) in zip(aa, l):
		a &= mask
		if a:
			a = a.bit_length()
		cnt[i, a] += 1
	res = [0] * (le + 1)
	for ((i, a), c) in cnt.items():
		if a:
			(base, baseidx) = ((a - i) * c, le - a)
		else:
			(base, baseidx) = (0, le - i)
		j = base
		for i in range(baseidx - 1, -1, -1):
			j += c
			res[i] += j
		j = base
		for i in range(baseidx, le + 1):
			res[i] += j
			j += c
	print(min(res))
main()


import itertools
n = int(input())
l = list(map(int, input().split()))
m = max(l) + 5
freq = [0 for _ in range(m)]
count = [0 for _ in range(m)]
vis = [-1 for _ in range(m)]
for i in range(n):
	q = [(l[i], 0)]
	pos = 0
	while len(q) > pos:
		(top, c) = q[pos]
		pos += 1
		if top >= m or vis[top] == i:
			continue
		vis[top] = i
		freq[top] += 1
		count[top] += c
		q.append((2 * top, c + 1))
		q.append((top // 2, c + 1))
ans = min((j for (i, j) in zip(freq, count) if i == n))
print(ans)


def main():
	input()
	aa = list(map(int, input().split()))
	(le, l) = (max(aa).bit_length(), [])
	for (i, a) in enumerate(aa):
		j = le - a.bit_length()
		aa[i] = a << j
		l.append(j)
	(mi, ma) = (min(aa), max(aa))
	a = mask = (1 << le) - 1
	if mi == ma:
		while mi == mi & a:
			mask = a
			a &= a << 1
	else:
		while mi != ma:
			mask &= mask << 1
			mi >>= 1
			ma >>= 1
		while not mi & 1:
			mask &= mask << 1
			mi >>= 1
	mask ^= (1 << le) - 1
	le = mask.bit_length() + 1
	res = [0] * le
	cache = {}
	for (a, i) in zip(aa, l):
		a &= mask
		if a:
			a = a.bit_length()
		tmp = cache.get((i, a))
		if tmp is None:
			cache[i, a] = tmp = [0] * le
			if a:
				(base, baseidx) = (a - i, le - a - 1)
			else:
				(base, baseidx) = (0, le - i - 1)
			(i, j) = (baseidx, base)
			while i:
				i -= 1
				j += 1
				tmp[i] = j
			(i, j) = (baseidx, base)
			while i < le:
				tmp[i] = j
				i += 1
				j += 1
		for (i, j) in enumerate(tmp):
			res[i] += j
	print(min(res))
main()


from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
pattern = set()
for a in A:
	p = []
	while a > 0:
		if a in pattern:
			break
		p.append(a)
		a = a // 2
	pattern |= set(p)

def check(v):
	ret = 0
	for a in A:
		count = 0
		while a != 0:
			if v == a or (v % a == 0 and v // a & -(v // a) == v // a):
				ret += len(bin(v // a)) - 3
				break
			if (v % a == 0 and v // a & -(v // a) == v // a) and a < v:
				return 1000000000000.0
			a = a // 2
			ret += 1
		else:
			return 1000000000000.0
	return ret
ans = 1000000000000.0
for p in pattern:
	ret = check(p)
	ans = ans if ans < ret else ret
print(ans)


read = lambda : map(int, input().split())
n = int(input())
a = list(read())
m = max(a) + 5
cnt = [0] * m
step = [0] * m
was = [-1] * m
for i in range(n):
	x = a[i]
	q = [(x, 0)]
	st = 0
	while st < len(q):
		(x, y) = q[st]
		st += 1
		if x >= m or was[x] == i:
			continue
		was[x] = i
		step[x] += y
		cnt[x] += 1
		q.append((x * 2, y + 1))
		q.append((x // 2, y + 1))
ans = min((step[x] for x in range(m) if cnt[x] == n))
print(ans)


def r(a):
	i = 0
	while not a % 2:
		a //= 2
		i += 1
	return (a, i)

def chem(n, A):
	(p, _) = r(A[0])
	for a in A:
		(q, _) = r(a)
		while p != q:
			if p > q:
				(p, q) = (q, p)
			(q, _) = r(q // 2)
		if q == 1:
			break
	t = 0
	L = []
	for a in A:
		(q, i) = r(a)
		while q != p:
			t += i + 1
			(q, i) = r(q // 2)
		L.append(i)
	L.sort()
	m = (L[n // 2] + L[(n - 1) // 2]) // 2
	return t + sum((abs(l - m) for l in L))

def main():
	n = readint()
	A = readintl()
	assert len(A) == n
	print(chem(n, A))
import sys
import time
import traceback
from contextlib import contextmanager
from io import StringIO

def readint():
	return int(input())

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

def readintl():
	return list(readinti())

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)

@contextmanager
def patchio(i):
	try:
		sys.stdin = StringIO(i)
		sys.stdout = StringIO()
		yield sys.stdout
	finally:
		sys.stdin = sys.__stdin__
		sys.stdout = sys.__stdout__

def do_test(k, test):
	try:
		log(f'TEST {k}')
		(i, o) = test
		with patchio(i) as r:
			t0 = time.time()
			main()
			t1 = time.time()
		if r.getvalue() == o:
			log(f'OK ({int((t1 - t0) * 1000000) / 1000:0.3f} ms)\n')
		else:
			log(f'Expected:\n{o}Got ({int((t1 - t0) * 1000000) / 1000:0.3f} ms):\n{r.getvalue()}')
	except Exception:
		traceback.print_exc()
		log()

def test(ts):
	for k in ts or range(len(tests)):
		do_test(k, tests[k])
tests = [('3\n4 8 2\n', '2\n'), ('3\n3 5 6\n', '5\n')]

def __starting_point():
	from argparse import ArgumentParser
	parser = ArgumentParser()
	parser.add_argument('--test', '-t', type=int, nargs='*')
	args = parser.parse_args()
	main() if args.test is None else test(args.test)
__starting_point()


n = int(input())
As = list(map(int, input().split()))

def solve(n, As):
	if n == 1:
		return 0
	Bs = [bin(a)[2:] for a in As]
	Bs = remove_common_area(Bs)
	long = max(map(len, Bs))
	costs = [0] * (long + 1)
	for b in Bs:
		update_costs(costs, b, long)
	return min(costs)

def remove_common_area(Bs):
	for i in range(1000):
		if len(Bs[0]) <= i:
			return [b[i:] for b in Bs]
		bi = Bs[0][i]
		for b in Bs[1:]:
			if len(b) <= i or b[i] != bi:
				return [b[i:] for b in Bs]
	return Bs

def update_costs(costs, b, long):
	len_b = len(b)
	found_1 = -1
	for i in range(long + 1):
		if found_1 == -1 and i < len_b and (b[i] == '1'):
			found_1 = i
		if found_1 == -1:
			costs[i] += abs(len_b - i)
		else:
			costs[i] += len_b - found_1 + i - found_1
print(solve(n, As))


N = 300000
(A, L, R, level, ans, H, UP) = ([0] * N, [0] * N, [0] * N, [0] * N, [0] * N, [0] * N, [0] * N)
x = 0
for i in range(N):
	level[i] = level[i // 2] + 1
n = int(input())
arr = list(map(int, input().rstrip().split()))
for i in range(n):
	A[i] = arr[i]
for i in range(n):
	x = A[i]
	H[x] += 1
	ans[1] += level[x] - level[1]
	while x != 1:
		if x & 1:
			R[x // 2] += 1
		else:
			L[x // 2] += 1
		x //= 2
result = ans[1]
up = False
i = 1
while i < N:
	if not L[i] and (not H[i]) and (not up):
		i = 2 * i + 1
	else:
		if 2 * i >= N:
			break
		if R[i] or H[i]:
			up = True
		UP[2 * i] += UP[i] + H[i] + R[i]
		i = 2 * i
	if i >= N:
		break
	if i & 1:
		ans[i] = ans[i // 2] - R[i // 2]
	else:
		ans[i] = ans[i // 2] + UP[i] - L[i // 2]
	result = min(result, ans[i])
print(result)


n = int(input())
a = [bin(int(i)) for i in input().split()]
j = 2
s = '0b'
while True:
	ok = True
	i = a[0]
	if j < len(i):
		c = i[j]
	else:
		c = '0'
	for i in a:
		if j < len(i):
			cc = i[j]
		else:
			cc = '0'
		if cc != c:
			ok = False
			break
	if not ok or j > 20:
		break
	s += c
	j += 1
b = []
r = 0
for i in a:
	pos = i.find('1', len(s))
	if pos == -1:
		b.append(len(i))
	else:
		b.append(pos)
		r += len(i) - pos
b.sort()
m = b[len(b) // 2]
for i in b:
	r += abs(i - m)
print(r)