class Array
	def accum
		inject([0]){|a, x| a + [a[-1] + x]}[1..-1]
	end

	def bsearch(l = 0, r = size - 1, &pred)
		return nil if l > r
		raise if l < 0 || r < 0 || l >= size || r >= size

		if r - l < 10
			return (l..r).find{|j| pred[self[j]]}
		end

		c = (l + r) / 2 
		if pred[self[c]]
			bsearch(l, c-1, &pred) || c
		else
			bsearch(c+1, r, &pred)
		end
	end
end



t = Time.new

n = gets.to_i
a = $<.map(&:to_i)
accum = a.accum
total = accum[-1]

subset_sum = -> i, j {
	raise "hage" if j >= accum.size

	if i <= j
		accum[j] - (i > 0 ? accum[i-1] : 0)
	else
		accum[-1] - accum[i-1] + accum[j]
	end
}

best = [
	subset_sum[0, a.size/3-1],
	subset_sum[a.size/3, a.size/3*2-1],
	subset_sum[a.size/3*2, a.size-1]
	].min

indices = (0..n-1).to_a

(0..a.size-1).each{|i|
	#p i
	j = indices.bsearch(i+1, n-1){|k| subset_sum[i, k-1] > best}
	j = indices.bsearch(0, i-2){|k| subset_sum[i, (k-1)%n] > best} unless j
	next unless j

	while (min = subset_sum[i, (j-1)%n]) * 3 <= total
		k = nil
		if i < j
			k = indices.bsearch(j+1, n-1){|l| min <= subset_sum[j, l-1]}
			k = indices.bsearch(0, i-1){|l| min <= subset_sum[j, (l-1)%n]} unless k
		else	
			k = indices.bsearch(j+1, i-1){|l| min <= subset_sum[j, (l-1)%n]}
		end

		best = min if k && subset_sum[k, (i-1)%n] >= min
		j = (j + 1) % n
	end
}

p best