Minimum Partition Sum

You are given an array of positive integers. Your task is to partition the array into maximal strictly increasing contiguous segments. In other words, each segment must consist of consecutive elements from the array such that every element (after the first) is strictly greater than the previous one.

For each segment, compute the sum of its elements. The minimum partition sum is defined as the sum of the sums of all these segments. Mathematically, if the array is partitioned into segments \(S_1, S_2, \dots, S_k\), then the answer is:

[ \text{Answer} = \sum_{i=1}^{k} \left( \sum_{x \in S_i} x \right) ]

Note: Because every number in the array is included in exactly one segment, the answer will always be equal to the sum of all elements in the array. However, the challenge is to implement the partitioning as described.

Example:

Input: 7
       4 2 3 6 1 7 8
Segments: [4], [2, 3, 6], [1, 7, 8]
Output: 4 + (2+3+6) + (1+7+8) = 31

inputFormat

The input is read from stdin and has the following format:

• The first line contains a single integer \(n\) denoting the number of elements in the array.
• The second line contains \(n\) space-separated positive integers.

It is guaranteed that \(n \geq 1\).

outputFormat

Output to stdout a single integer — the minimum partition sum of the array.

## sample

7
4 2 3 6 1 7 8

31