Coat of Anticubism
Contest: Codeforces Round 349 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, geometry

As some of you know, cubism is a trend in art, where the problem of constructing volumetrical shape on a plane with a combination of three-dimensional geometric shapes comes to the fore.

A famous sculptor Cicasso, whose self-portrait you can contemplate, hates cubism. He is more impressed by the idea to transmit two-dimensional objects through three-dimensional objects by using his magnificent sculptures. And his new project is connected with this. Cicasso wants to make a coat for the haters of anticubism. To do this, he wants to create a sculpture depicting a well-known geometric primitive — convex polygon.

Cicasso prepared for this a few blanks, which are rods with integer lengths, and now he wants to bring them together. The i-th rod is a segment of length li.

The sculptor plans to make a convex polygon with a nonzero area, using all rods he has as its sides. Each rod should be used as a side to its full length. It is forbidden to cut, break or bend rods. However, two sides may form a straight angle $$180^\circ$$.

Cicasso knows that it is impossible to make a convex polygon with a nonzero area out of the rods with the lengths which he had chosen. Cicasso does not want to leave the unused rods, so the sculptor decides to make another rod-blank with an integer length so that his problem is solvable. Of course, he wants to make it as short as possible, because the materials are expensive, and it is improper deed to spend money for nothing.

Help sculptor!

Input format:
The first line contains an integer n (3 ≤ n ≤ 105) — a number of rod-blanks.

The second line contains n integers li (1 ≤ li ≤ 109) — lengths of rods, which Cicasso already has. It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has.

Output format:
Print the only integer z — the minimum length of the rod, so that after adding it it can be possible to construct convex polygon with (n + 1) vertices and nonzero area from all of the rods.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example triangle with sides {1 + 1 = 2, 2, 1} can be formed from a set of lengths {1, 1, 1, 2}.

In the second example you can make a triangle with lengths {20, 11, 4 + 3 + 2 + 1 = 10}.

Example input:
3
1 2 1

Example output:
1

Example input:
5
20 4 3 2 1

Example output:
11

Editorial:
You are given n lenghs li. Add to them the least possible length l, so that a polygon can be folded of them. We show that the polygon can be folded out of the lengths li only when the maximum length strictly less than the sum of remaining. It follows that we need to add a length which equals $$l = 2 \cdot \max(l_i) - \sum_{i=1}^{n} l_i + 1$$, so much the sum of the small parties is not enough to surpass the greater one.
1. Let r1, r2, ..., rm — a set of a convex polygon points in the traversal order. Then $$\rho(r_1,r_m) < \sum_{k=2}^{m}\rho(r_{k-1},r_k)$$, where ρ(r1, r2) — Euclidean distance between points r1 и r2. Prove by induction. If n = 3 it is the same as a triangle inequality. The assertion is true for all m ≤ n. Consider a system of n + 1 points. $$\rho(r_1,r_n) < \sum_{k=2}^{n}\rho(r_{k-1},r_k)$$ by the hypothesis of the induction. Hence $$\rho(r_{1},r_{n+1})<\rho(r_{1},r_{n})+\rho(r_{n},r_{n+1})<\sum_{i=2}^{n+1}\rho(r_{k-1},r_{k})$$. The assertion is proved.
2. Let A = {li} — a set of lengths the maximum of which is strictly less than the sum of the rest. Then, a convex polygon can be formed out of them. We can show a structure: let's consider a circle with a diameter which is the largest side max(li). Now, let's draw a chain of chords, the length of which coincides with the lengths li, out of the circle. We have three options - either it has coincided with the second pointer of a diameter, that is cool, or do not reach it, or pass through it. Note that if we increase the diameter of the circle, recording the longest side of a polygon in a chord, then the length of the smaller arc will decrease monotonically, approaching to the chord length, and the length of a greater arc will increase monotonically. Thus, if we have not reached the other end of the diameter then we expand the radius, remaining in the smallest half of the circle, and otherwise we expand it, remaining in the biggest half. If it is a sufficiently large radius, we will move on from this point and will find ourselves on the other side. As the function of the dependence of the angular distance of the last point of the chain is continuous and there is such transition, according to Bolzano-Cauchy theorem we can state that there is a point at which the extreme point of the chain and the second point of the diameter will coincide, thus forming the very convex polygon.
Generally speaking, if you do not go into formalism, this quality can be easily derived from physical considerations — on the one hand, there is no way to hold the broken path between two points shorter than on a straight line segment. On the other hand, imagine that the longest side is two nails driven into the wall, which is connected to both ends of the chain of solid rods with a predetermined length. Then, being weighed down, this chain will just form the convex polygon.