题目描述

AC鸭知道所有内角均小于或等于180°的图形是凸多边形。现在AC鸭有 $n$ 条边，这 $n$ 条边不能组成凸多边形，他想知道至少需要增加一条多长的边才能使得这些边能组成一个凸多边形。注意：多条边平行放置且首尾相连时可以组成一条边。

输入

第一行包含一个整数 $n$ ($3 ≤ n ≤ 10^5$)。

第二行包含 $n$ 个整数 $l_i$ ($1 ≤ l_i ≤ 10^9$)，表示所有已有边的长度。

输出

打印唯一的整数，表示 添加的一条边最小的长度。

样例

3
1 2 1

1

数据范围

子任务一：30分，满足$3 ≤ n ≤ 10$；

子任务二：30分，满足$3 ≤ n ≤ 10^3$；

子任务三：40分，满足$3 ≤ n ≤ 10^5$。

在第一个示例中，边为 {1 + 1 = 2, 2, 1} 的三角形可以由一组长度 {1, 1, 1, 2} 的边形成。