Minimum Sum of Largest Elements

Given an array A of n integers, you are asked to partition the array into one or more contiguous subarrays. From each subarray, select the largest element and take their sum. Although the problem sounds complex, it turns out that the optimal partitioning always results in a sum equal to the maximum element of the whole array when n > 1. In the case when n = 1, the answer is simply the single element itself.

Problem Clarification:

• If the array has only one element, output that element.
• Otherwise, the answer is the maximum element in the entire array.

The result needs to be computed efficiently.

Mathematical Formulation:

Let \(A = [a_1, a_2, \dots, a_n]\). Then the answer is:

\[ \text{answer} = \begin{cases} a_1, & n = 1, \\ \max (A), & n > 1. \end{cases} \]</p>

inputFormat

The first line of input contains a single integer n (the number of elements in the array).

The second line contains n space-separated integers representing the array A.

outputFormat

Output a single integer, the minimum sum of the largest elements from each subarray of an optimal partition. According to the problem, if n > 1 this is equivalent to outputting \(\max (A)\), otherwise it is the only element in the array.

## sample

1
5

5

</p>