You are a young and talented engineer working at MegaFon — one the largest telecommunication companies in Russia. Your current project aims to improve mobile internet experience by dynamically allocating outgoing traffic limits for each user based on the current consumption.

As a subtask of this project you are given a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ that describes communication between user's phone and your transmitter for some period of $$$n$$$ consecutive seconds. Value $$$a_i$$$ equals to the difference between traffic sent and traffic received during second $$$i$$$, thus, this values can be positive, negative, or equal to zero.

For any sequence of traffic differences $$$b_1, b_2, \ldots, b_k$$$ you define its weak estimation as the sum of maximums of all pairs of adjacent elements, i.e. $$$f(b_1, b_2, \ldots, b_k) = \sum_{i = 1}^{k - 1} \max(b_i, b_{i + 1})$$$. Note that weak estimation of empty sequence equals to $$$0$$$.

For traffic scheduling you plan to use strong estimation of sequence $$$a$$$ that you define as the maximum value of weak estimation among all subsequences of $$$a$$$. Recall that subsequence is any sequence that you can obtain by removing some elements of the original sequence. Empty subsequence and subsequence equal to the given sequence are also allowed. The task here is to develop a fast algorithm that computes strong estimation of any given sequence.