Minimum Cost Tree From Leaf Nodes

Given an array/list ‘ARR' of size ‘N’, the task is to generate a Complete Binary Tree in such a way that the sum of the non-leaf nodes is minimum, whereas values of the leaf node correspond to the array elements in an In-order Traversal of the tree and value of each non-leaf node corresponds to the product of the largest leaf value in the left sub-tree and right sub-tree.

Example:

Let's say we have an 'ARR' = {1, 2, 3, 4}, so the possible complete 
binary trees will be:
   4                                                          12                      
  /  \                                                       /  \
 1   8                                                      6    4
     / \                                                   /  \
   2   12                                                  2   3   
        /  \                                              /  \
        3   4                                             1   2
  Sum of non-leaf nodes  = 24                    Sum of non-leaf nodes = 20
  So the required answer you have to return is 20.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of array elements.

The second line of every test case contains 'N' space-separated integers denoting the inorder traversal of leaf nodes of a complete binary tree.

Output format:

For each test case, return the minimum possible sum of non-leaf nodes of a binary tree.

Output for each test case is printed on a separate line.

Note:

1.You do not need to print anything, it has already been taken care of. Just return the minimum possible sum of all non-leaf nodes.

2. It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

Constraints:

1 <= T <= 10
2 <= N <= 40
1 <= ARR[i] <= 15

Where ‘ARR[i]’ represents the array elements.

Time limit: 1 sec