##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
| # | Title | Points | Solved | Admin | |
|---|---|---|---|---|---|
You are given an array of length .
In one operation, you choose a position between two adjacent elements of the current array and split it into a non-empty prefix and a non-empty suffix. Then you choose one of these two parts and delete it.
The cost of the operation is equal to the maximum value among the deleted elements.
Your goal is to perform operations until exactly one element remains. Find the minimum possible total cost.
Here, is the minimum possible total cost.
The array already contains exactly one element, so no operation is needed.
One optimal way is to split the array into [3, 1] and [4], then delete [3, 1]. The cost is , and only the number remains.
One optimal way uses three operations. First delete [5, 0] with cost . The remaining array is [100, 0, 4]. Then delete [4] with cost . Finally delete [0] with cost . The total cost is , and only remains.