题目描述

芯芯继续在神秘的大陆上冒险，这一次，她来到了由魔法阶梯搭建成的一座高塔。塔的每一级阶梯上都标着一个神秘的能量值：

• 芯芯可以从任意一级阶梯开始攀登；
• 每次只能跳到能量值更大的后面某一级阶梯；
• 跳跃方向必须是从左到右，也就是说只能往后跳，不能回头；
• 每登上一阶，就能累加那一级阶梯的能量值；
• 她想要攀登出能量值总和最大的路线！

当然，芯芯也可以选择什么都不做（如果所有能量值都是下降的，她可以直接放弃），此时获得的能量为 $0$。

请你帮芯芯计算，她最多能够获得多少能量值！

输入格式

• 第一行包含一个整数 $n$，表示阶梯的数量。$(1 \leq n \leq 10^3)$
• 第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个阶梯上的能量值。$(0 \leq a_i \leq 10^6)$

输出格式

• 输出一个整数，表示芯芯能够收集到的最多能量值。