System Charge Combination

You are given an array charge of size n, where charge[i] represents the charge value of a system.

You must remove all systems one by one until only a single system remains. The goal is to perform these removals in an order that maximizes the charge of this final remaining system.

The operation is defined as follows:

1) When you select and remove a system, its immediate left and right neighbors (if they exist) merge.

2) The new merged system has a charge equal to the sum of the charges of the two neighbors that were merged.

3) Systems at the ends of the current array (the first or last) cannot cause a merge when removed, as they only have one neighbor.

Your task is to find the maximum possible charge of the final system.

Input Format:

The first line of input contains an integer 'N', the size of the array.

The second line contains 'N' space-separated integers, representing the elements of the charge array.

Output Format:

Print a single integer representing the maximum possible charge of the final system.

Note:

A simple greedy approach does not work. The optimal strategy often involves removing elements that result in a smaller immediate merge cost to set up a larger merge later.