A maintenance crew monitors a pipeline instrumented with a row of n pressure sensors, numbered from the pipeline's inlet. Before a scheduled shutdown, the pipeline must be logically split into exactly three consecutive segments (in sensor order), and the first segment must start at the very first sensor. Recalibrating a segment costs exactly the pressure reading shown at the sensor where that segment begins. The crew wants to choose the two remaining split points -- cutting the line into 3 consecutive, non-empty segments -- to minimize the total recalibration cost, which is the sum of the three segments' opening readings.

Input format

Line 1: a single integer n -- the number of sensors. Line 2: n space-separated integers reading[0], reading[1], ..., reading[n-1] -- the pressure reading at each sensor, in pipeline order.

Output format

Print a single integer: the minimum possible total recalibration cost over all ways to split the n sensors into exactly 3 consecutive, non-empty segments where the first segment begins at sensor 0.

Constraints

• 3 <= n <= 50
• 0 <= reading[i] <= 50 for every valid i

5
4 1 2 3 8

7

3
5 5 5

15