# coding: utf-8
import random

# GA

n = input()
m = []
for i in range(n):
    m.append(input())

def generateGene():
    tmp = []
    table = m[:]
    for x in xrange(n):
	i = random.randint(0,len(table)-1)
	tmp.append(table[i])
	del(table[i])
    return tmp

class Solution:
    def __init__(self, gene):
        self.gene = gene
	self.value = 0
	if(len(gene)!=0):
	    self.eval()
    def eval(self):
	discount = 0
	for c in self.gene:
	    self.value += max(c-discount,0)
	    discount = (discount+c)%1000

NUM_POP = 10 # 少なくとも2以上かつ偶数にして
GENERATION = 20

# 最初の個体群をランダム生成
pop = [Solution(generateGene()) for x in xrange(NUM_POP)]

for gc in xrange(GENERATION):

    min_val = sum(m)
    max_val = -1
    top_index = -1
    top2_index = -1

    # 評価補助テーブル生成
    for i,s in enumerate(pop):
	if(s.value < min_val):
	    min_val = s.value
	    top2_index = top_index
	    top_index = i
	if(s.value > max_val):
	    max_val = s.value


    #print "max:", max_val, "min:", min_val

    pickup_table = [0]*n
    probability_sum = 0
    for i in xrange(n):
	pickup_table[i] = max_val - pop[i].value
	probability_sum += pickup_table[i]

    # 評価の高さに基づいた確率により個体を交叉させ新個体を生成
    left = NUM_POP - 2
    #new_pop = [Solution(pop[top_index].gene[:]),Solution(pop[top2_index].gene[:])]
    top_s = Solution([])
    top_s.gene = pop[top_index].gene[:]
    top_s.eval()
    top2_s = Solution([])
    top2_s.gene = pop[top2_index].gene[:]
    top2_s.eval()
    new_pop = [top_s, top2_s]
    #print "top:", top_s.value, top_s.gene

    while(left>0):
	# 2個体pickする
	sum1 = 0
	sum2 = 0
	r1 = random.randint(0,probability_sum)
	r2 = random.randint(0,probability_sum)
	for s in pop:
	    sum1 += s.value
	    if(sum1>=r1):
		solution1 = s
		break
	for s in pop:
	    sum2 += s.value
	    if(sum2>=r2):
		solution2 = s
		break
		
	# 二点交叉
	a,b = (random.randint(0,n),random.randint(0,n))
	first, second = min(a,b), max(a,b)
	new1 = Solution([])
	new1.gene = solution1.gene[:] 
	new2 = Solution([])
	new2.gene = solution2.gene[:] 
	for i in range(first, second):
	    new1.gene[i] = solution2.gene[i]
	    new2.gene[i] = solution1.gene[i] 
	
	new1.eval()
	new2.eval()
	# 生成した新個体をテーブルに追加
	new_pop.append(new1)
	new_pop.append(new2)
	left -= 2
    pop = new_pop

top = pop[0] 
for s in pop:
    if(s.value < top.value):
	top = s

print top.value