题目描述

小珅在玩一款游戏，里边包含若干关卡，可以从头往后挑一些关卡打，每个关卡有不同难度，当挑战了一个关卡后，只能选择后边的关卡继续游戏，小珅热爱挑战难度，他希望每次挑战的关卡难度是递增的，并且挑战的所有关卡难度和最大，他想知道这个最大值是多少。

输入格式

第一行输入一个整数 n，代表总关卡数。

接下来一行输入 n 个整数，a1, a2, a3, …, an，代表矩阵这一行的 n 个数。

（1 ≤ n ≤ 10^4，1 ≤ ai ≤ 10^9）

输出格式

输出一个整数，代表小珅挑战的关卡的难度和的最大值。

输入样例 #1

3
1 3 2

输出样例 #1

4

输入样例 #2

10
823564441 115438166 784484493 74243043 114807988 137522504 441282328 16531730 823378841 143542613

输出样例 #2

1723301500

输入样例 #3

8
9 8 7 6 5 5 1 1

输出样例 #3

9

数据范围与约定

1 ≤ n ≤ 10^4；1 ≤ ai ≤ 10^9。