26105번 - Folding Stick 다국어

문제

There is a folding stick made up of $n$ segments of positive length. The segments are connected by hinges (stretchable strings), allowing the segments to be folded 180ドル$ degrees at each hinge. The wrapping length is said to be the length of the folded stick after the stick is folded at hinges one or more. Depending on the folding strategy, the wrapping length may be different.

You are to find the minimum wrapping length under the condition that the stick is folded in the following way: First, place the segments of the stick along a horizontal line. Then, fold the stick clockwise from left to right. During folding, the segment attached to the left side of each hinge rotates 180 degrees clockwise or not at all.

For example, the figure below shows a four-segment stick with a sum of segment lengths of 10ドル$. In the figure, the lengths of the segments are 3ドル,ドル 2ドル,ドル 2ドル,ドル and 3ドル$ from left to right, and the hinges are marked with 1, 2, 3.

In this example, the stick cannot be folded at both hinges 1 and 2. This is because if the stick is folded at hinge 1 and then at hinge 2, the segment with length 3 passing over the hinge 2 will be broken. If it is folded only at hinge 2, the wrapping length is 5. If it is folded at hinges 1 and 3 in order, the wrapping length is 4 as shown in the figure below.

Given a sequence of segments lengths of a folding stick, write a program to output the minimum wrapping length of the stick.

입력

Your program is to read from standard input. The input starts with a line containing an integer, $n$ (2ドル ≤ n ≤ 100,000円$), where $n$ is the number of segments of a folding stick. The next line contains $n$ positive integers which represent a sequence of lengths of segments from the leftmost one to rightmost one of the stick. Each segment length is no more than 20ドル,000円$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the positive integer representing the minimum wrapping length.

제한

힌트