Minimum Start Value

Given an integer array, find the smallest positive initial value x such that, when the elements are added from left to right, every prefix sum is at least 1.

输入格式

The first line contains n (1..100000); the second line contains n integers arr[i] (−10^6..10^6).

输出格式

Output the smallest valid initial value x.

样例 1

输入：

10
-5 4 -2 3 1 -1 -6 -1 0 5

输出：

8

样例 2

输入：

5
-5 4 -2 3 1

输出：

6

样例 3

输入：

3
1 2 3

输出：

1