Description

Ryanzi 最近沉迷于金铲铲，但是 guanmiantang_h 想拉她去写题，于是 Ryanzi 决定修炼隐身技能让 guanmiantang_h 找不到她。

Ryanzi 初始的隐身技能值为 $0$，每一天开始时，她可以选择当天是否进行修炼，每天的修炼可以增长不同点数的隐身技能值。但是修炼隐身技能实在是太累了，所以如果当天修炼了隐身技能，Ryanzi 至少需要休息一天才能进行下一次修炼， 聪明的你来帮 Ryanzi 算一算，$n$ 天之后，她的隐身技能值最高是多少？

Format

Input

第一行包含一个整数 $n\ (1\leq n\leq10^5)$，表示总天数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n\ (-10^9\leq a_i \leq 10^9)$，表示每一天可以增长的技能值。

Output

输出一个整数，表示 $n$ 天后 Ryanzi 隐身技能值的最大值。

Samples

5
-5 0 5 10 1

10

Limitation

1s, 1024KiB for each test case.