你是 MegaFon（俄罗斯最大的电信公司之一）的一名年轻且有才华的工程师。你当前的项目旨在通过根据当前消耗量动态分配每个用户的出口流量限制，来改善移动互联网体验。

作为该项目的一个子任务，你被给定了一个整数序列 $a_1, a_2, \dots, a_n$，它描述了用户手机与你的发射机在连续 $n$ 秒内的通信情况。值 $a_i$ 等于第 $i$ 秒发送的流量与接收的流量之差，因此这些值可以是正数、负数或零。

对于任何流量差序列 $b_1, b_2, \dots, b_k$，你将其“弱估计值”（weak estimation）定义为所有相邻元素对的最大值之和，即 $f(b_1, b_2, \dots, b_k) = \sum_{i=1}^{k-1} \max(b_i, b_{i+1})$。注意，空序列的弱估计值为 $0$。

为了进行流量调度，你计划使用序列 $a$ 的“强估计值”（strong estimation），定义为 $a$ 的所有子序列中弱估计值的最大值。回想一下，子序列是指通过删除原始序列中的某些元素而获得的任何序列。空子序列和等于原序列的子序列也是允许的。任务是开发一个快速算法来计算给定序列的强估计值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示序列 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)。

输出格式

输出一个整数，即序列 $a$ 的强估计值。

样例

输入 1

4
5 -3 -2 1

输出 1

6

输入 2

4
-1 -1 -1 -1

输出 2

0