4758: 木棍
内存限制：256 MB
时间限制：1 S
题面：传统
评测方式：文本比较
上传者：
提交：14
通过：7
题目描述
N根木棒，保证不能组成三角形，添加一根长度最短的木棒，使其能组成三角形
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 ob
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
. 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
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
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.
Examples
Input
3 1 2 1
Output
1
Input
5 20 4 3 2 1
Output
11
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}.
输入格式
输入的第一行N（1<=n<=2*10^5）,木棒的个数。
第二行包含一个长为 N根木棒的各自的长短0 。
输出格式
输出一行，所需木棒的长度
Examples
Input
3 1 2 1
Output
1
Input
5 20 4 3 2 1
Output
11
输入样例 复制
3
1 2 1输出样例 复制
1