There are n boxes with colored balls on the table. Colors are numbered from 1 to n. i-th box contains a_{i} balls, all of which have color i. You have to write a program that will divide all balls into sets such that:  each ball belongs to exactly one of the sets,  there are no empty sets,  there is no set containing two (or more) balls of different colors (each set contains only balls of one color),  there are no two sets such that the difference between their sizes is greater than 1. 

Print the minimum possible number of sets.


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 500).

The second line contains n integer numbers a_1, a_2, ... , a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print one integer number — the minimum possible number of sets.


-----Examples-----
Input
3
4 7 8

Output
5

Input
2
2 7

Output
4



-----Note-----

In the first example the balls can be divided into sets like that: one set with 4 balls of the first color, two sets with 3 and 4 balls, respectively, of the second color, and two sets with 4 balls of the third color.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import time
import sys
from math import sqrt
n = int(input())
a = list(map(int, input().split()))
sq = int(sqrt(a[0])) + 2
s = set()
for box in range(1, sq):
	if a[0] % box == 0:
		s.add(a[0] // box)
		s.add(a[0] // box - 1)
	else:
		s.add(a[0] // box)
for balls in range(1, sq):
	if a[0] % balls <= a[0] // balls:
		s.add(balls)
for size in sorted(s, reverse=True):
	ans = 0
	for x in a:
		if x / size >= x % size:
			ans += (x + size) // (size + 1)
		else:
			break
	else:
		print(ans)
		return


def judge(lists, x):
	ans = 0
	for i in lists:
		t = i // x
		d = i % x
		if d == 0:
			ans += t
		elif t + d >= x - 1:
			ans += t + 1
		else:
			return -1
	return ans
while True:
	try:
		n = input()
		balls = list(map(int, input().split()))
		minn = min(balls)
		for i in range(1, minn + 1):
			if judge(balls, minn // i + 1) >= 0:
				ans = judge(balls, minn // i + 1)
				break
			elif judge(balls, minn // i) >= 0:
				ans = judge(balls, minn // i)
				break
		print(ans)
	except EOFError:
		break


3
import sys
n = int(sys.stdin.readline())
a = [int(x) for x in sys.stdin.readline().split()]

def is_valid(s, k):
	y = s % k
	return s // k >= y

def all_valid(a, k):
	for s in a:
		if not is_valid(s, k):
			return False
	return True
best_sol = 1
k = 1
while k * k <= a[0]:
	if all_valid(a, k):
		best_sol = max(best_sol, k)
	k += 1
t = 1
while t * t <= a[0]:
	k = a[0] // t
	if all_valid(a, k):
		best_sol = max(best_sol, k)
	if a[0] % t == 0 and k > 1:
		if all_valid(a, k - 1):
			best_sol = max(best_sol, k - 1)
	t += 1
print(sum((s // (best_sol + 1) + (0 if s % (best_sol + 1) == 0 else 1) for s in a)))


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

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

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return fac

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
a = list(map(int, input().split()))
sq = int(math.sqrt(a[0])) + 2
s = set()
for box in range(1, sq):
	if a[0] % box == 0:
		s.add(a[0] // box)
		s.add(a[0] // box - 1)
	else:
		s.add(a[0] // box)
for balls in range(1, sq):
	if a[0] % balls <= a[0] // balls:
		s.add(balls)
for size in sorted(s, reverse=True):
	ans = 0
	for x in a:
		if x / size >= x % size:
			ans += (x + size) // (size + 1)
		else:
			break
	else:
		print(ans)
		exit()


from math import sqrt

def divide_into_p(p, a):
	q = a // (p + 1)
	r = a % (p + 1)
	if r == 0:
		return q
	elif q + r >= p:
		return q + 1
	else:
		return None

def divisible_into_p(p, lst):
	lgth = 0
	for l in lst:
		dp = divide_into_p(p, l)
		if dp == None:
			return None
		else:
			lgth += dp
	return lgth

def index_lst(a, sqrta):
	lst = []
	for i in range(1, sqrta + 1):
		p = a // i
		lst.append(p)
		if not a % p:
			lst.append(p - 1)
	for i in range(sqrta + 1, 0, -1):
		lst.append(i)
	return lst

def check_all_p(balls):
	a = balls[0]
	sqrt_a = int(sqrt(a))
	indices = index_lst(a, sqrt_a)
	for i in indices:
		dp = divisible_into_p(i, balls)
		if dp != None:
			return dp
input()
balls = sorted([int(x) for x in input().split()])
print(check_all_p(balls))


from math import sqrt
n = int(input().strip())
ais = list(map(int, input().strip().split()))
ais.sort(reverse=True)
xmax = int(sqrt(ais[0]))

def check(x):
	q = 0
	for ai in ais:
		qi = -(-ai // (x + 1))
		q += qi
		if x * qi > ai:
			return (False, None)
	else:
		return (True, q)
qbest = sum(ais) + 1
for x in range(1, xmax + 1):
	(valid, q) = check(x)
	if valid:
		qbest = min(qbest, q)
for k in range(1, xmax + 1):
	x = ais[0] // k
	(valid, q) = check(x)
	if valid:
		qbest = min(qbest, q)
	if ais[0] % k == 0:
		x -= 1
		(valid, q) = check(x)
		if valid:
			qbest = min(qbest, q)
print(qbest)


n = int(input().rstrip())
s = input()
a = [int(ch) for ch in s.split()]
a = a[0:n]
a.sort()

def check_num(p, i):
	max_b = i // (p + 1)
	b = i % p + (max_b - i % p) // p * p
	cur = (i - b) // p
	if b < 0:
		return None
	return cur

def sets_num(p):
	total = 0
	for i in a:
		if check_num(p, i):
			total += check_num(p, i)
		else:
			return None
	return total
for div_sets in range(1, a[0] + 1):
	(p, q) = divmod(a[0], div_sets)
	if q == 0:
		if sets_num(p):
			print(sets_num(p))
			break
		if p > 0 and sets_num(p - 1):
			print(sets_num(p - 1))
			break
	elif sets_num(p):
		print(sets_num(p))
		break


def pay(coin, amount):
	if amount // coin < amount % coin:
		return -1
	if amount < coin * (coin + 1):
		return amount // coin
	return (amount - 1) // (coin + 1) + 1

def pay_all(coin):
	sum = 0
	for i in range(n):
		p = pay(coin, a[i])
		if p == -1:
			return -1
		sum += p
	return sum
n = int(input())
a = list(map(int, input().split()))
amin = min(a)
coin = amin
k = 1
p = -1
while p == -1:
	p = pay_all(coin)
	if p == -1 and amin % coin == 0:
		p = pay_all(coin - 1)
	k += 1
	coin = amin // k
print(p)