题目内容

给定 $n$ 个正整数组成的数组 $a$。请在所有连续且严格升序的子数组中，找出元素和最大的那一段，输出这个和。

严格升序是指从左到右，每个数都比它前一个数大。相邻两数相等时，升序在这里断开，相等的两个数不能放进同一段。只含一个元素的子数组也算严格升序，它的和就是这个元素本身。

输入描述

第一行一个整数 $n$。

第二行 $n$ 个正整数 $a_i$。

约束

$1 \le n \le 10^5$

$1 \le a_i \le 10^9$

子数组的和可能超过 $32$ 位有符号整数的范围，计算时使用 $64$ 位整数。

输出描述

输出一个整数，表示严格升序连续子数组的最大元素和。

样例1

输入

6
10 20 30 5 10 50

输出

65

说明

$10+20+30=60$，$5+10+50=65$。取较大的 $65$。

样例2

输入

5
9 6 4 3 1

输出

9

说明

数组严格递减，每一段都只有一个数。答案是其中最大的元素 $9$。

样例3

输入

6
1 3 3 4 5 2

输出

12

说明

$1+3=4$。第二个 $3$ 与前一个相等，升序断开。接着 $3+4+5=12$，$2$ 单独成段。答案是 $12$。