正如你们中的一些人所知,立体主义是一种艺术趋势,其中通过三维几何形状的组合在平面上构建体积形状的问题脱颖而出。
著名雕塑家西加索讨厌立体主义,你可以欣赏他的自画像。更令他印象深刻的是,通过他宏伟的雕塑作品,将二维物体通过三维物体进行传递。他的新项目与此有关。西加索想为反立体主义的仇恨者制作一件外套。为此,他想要创作一个雕塑来描绘一种著名的几何基元——凸多边形。
西加索为此准备了一些毛坯,它们是整数长度的杆,现在他想将它们组合在一起。第 i 根杆是长度为 li 的一段。
雕塑家计划使用他拥有的所有杆作为其边,制作一个面积非零的凸多边形。每根杆都应用作其全长的一侧。禁止切割、折断或弯曲棒材。然而,两条边可以形成直角$$180^\circ$$。
西加索知道不可能用他选择的长度的杆制作出面积非零的凸多边形。西加索不想留下未使用的杆,因此雕塑家决定再制作一个整数长度的杆毛坯,这样他的问题就可以解决。当然,他希望能尽量短,因为材料很贵,花钱不劳而获是不正当的行为。
帮助雕塑家!
输入
第一行包含一个整数 n (3 ≤ n ≤ 105) — 棒坯的数量。
第二行包含 n 个整数 li (1 ≤ li ≤ 109) — 杆的长度,Cicasso 已经有了。可以保证使用 Cicasso 已有的杆不可能制作具有 n 个顶点和非零面积的多边形。
输出
打印唯一的整数 z — 杆的最小长度,这样在添加它之后就可以从所有杆构造具有 (n + 1) 个顶点和非零面积的凸多边形。
示例
输入 #1
3 1 2 1
输出 #1
1
输入 #2
5 20 4 3 2 1
输出 #2
11
注意
在第一个示例中,边长为 {1 + 1 = 2, 2, 1} 的三角形可以由一组长度 {1, 1, 1, 2} 形成。
在第二个示例中,您可以制作一个长度为 {20, 11, 4 + 3 + 2 + 1 = 10} 的三角形。