Background

你正在玩逃离地下城的游戏，并打到了第 $999$ 层，下一层就要面对大魔王了。

Description

这一层中有 $n$ 个房间，每个房间中只有怪物或医疗包。若第 $i$ 个房间中是怪物，则你需要消耗 $a_i$ 点血量击败怪物；若第 $i$ 个房间中是医疗包，则你可恢复 $a_i$ 点血量。若你的血量降低到 $\le 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