阿Q拿到了一排数，他想知道其中的最大非空子段和是多少。

输入格式

第一行输入一个整数 n 代表这排数的个数。

第二行输入 n 个整数 $a_1,a_2,a_3\cdots a_n$，分别代表 n 个数。$(1 \leq n \leq 10^6,-10^9 \leq a_i \leq 10^9)$

输出格式

输出一个整数，代表最大非空子段和，占一行。

样例输入

3
1 -2 3

样例输出

3