Background

你正在玩一个闯关游戏，打到了第 $999$ 关，下一关就要面对大魔王了。

Description

这一关中有 $n$ 个房间，若第 $i$ 个房间中是怪物，则你需要消耗 $a_i$ 点血量击败怪物，否则你可以回复 $a_i$ 点血量。

若你的血量降低到小于等于 $0$，则闯关失败。

在这关你必须按顺序经过每个房间，也就是说在进入第 $i$ 个房间之前必须通过前 $i-1$ 个房间。

请计算出初始时你至少需要多少血量才能通过这一关。

Format

Input

一行输入一个整数 $n$ ($1 \le n \le 10^6$)，表示房间的数量。

一行输入 $n$ 个空格分隔的整数 $a_i$ ($-10^6 \le a_i \le 10^6$)，若 $a_i<0$，则表示在这个房间你会失去 $a_i$ 点血量，否则表示你在这个房间可以回复 $a_i$ 点血量。

Output

一行输出一个整数，表示通过本关需要的最小初始血量。

Samples

3
-100 -200 -300

601

5
-200 -300 1000 -100 -100

501