CF667B Coat of Anticubism

如你所知，立体主义是一种艺术流派，重点在于用多个三维几何形状在平面上构建体积形状的问题。 著名的雕塑家 Cicasso（你可以欣赏到他的自画像）讨厌立体主义。他更倾向于用他精美的雕塑，通过三维物体来表达二维物体。现在他的新项目正是与此相关。Cicasso 想为反对立体主义的人们制作一件大衣。为此，他计划创造一个描绘著名几何元素——凸多边形的雕塑。 Cicasso 已经准备好了一些原材料，这些原材料是若干长度为整数的棍子，第 $i$ 根棍子的长度为 $l_i$。 雕塑家计划用他所有的棍子作为边长，完整地制作一个面积非零的凸多边形。每根棍子都必须作为一条边使用且长度不可更改。禁止截断、折断或弯曲棍子。不过，可以有两条边组成的角为 $180^\circ$。 Cicasso 已经知道，假如只用他已经拥有的这些长度的棍子，不可能做出一个面积非零的凸多边形。Cicasso 不想留下任何未使用的棍子，因此他决定再制作一根整数长度的新棍子，使得问题变得可解。当然，他希望这根棍子尽可能短，因为材料昂贵，浪费是不妥的行为。 请你帮助雕塑家！

第一行包含一个整数 $n$（$3 \leq n \leq 10^5$）——棍子的数量。 第二行包含 $n$ 个整数 $l_i$（$1 \leq l_i \leq 10^9$）—— Cicasso 已经拥有的这些棍子的长度。保证仅用这些长度无法组成一个 $n$ 边、面积非零的多边形。

输出一个整数 $z$，表示最短的新棍子的长度，使得将其加入现有棍子后，可以用所有的棍子构成一个 $n+1$ 边、面积非零的凸多边形。

在第一个样例中，可以用 $1+1=2,2,1$ 组成一个三角形，因此长度集合 $\{1,1,1,2\}$ 可以形成一个多边形。 在第二个样例中，可以用 $20,11,4+3+2+1=10$ 组成一个三角形。 由 ChatGPT 5 翻译