Minimum Cost to Reduce Array

Given an array ARR of size N containing positive integers, the task is to reduce the size of the array to 1 by performing a specific operation multiple times. In one operation, you can merge any two adjacent elements of the array, and the cost of merging will be the sum of those two elements. Determine the minimum total cost of reducing the array to one element by using this operation.

Input:

int T - the number of test cases.
int N - the size of the array for each test case.
List of integers ARR - the array elements for each test case.

Output:

The minimum cost required to reduce the array to one element for each test case.

Example:

Input:

2
3
4 6 8
4
1 2 3 4

Output:

36
19

Explanation:

For the first test case, optimal way to merge would be (4, 6) → (10, 8), then (10, 8) → 18, that gives a total cost of 18 + 10 = 36.

For the second test case, optimal way to merge would be (1, 2), (3, 4), and then the result of these merges, giving a total cost of 19.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 100
• 1 <= ARR[i] <= 10⁶
• Time Limit: 1 sec

Note:

The operation will be performed N-1 times for an array of size N.