output_description: Print the minimum possible total cost incurred.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      a_1 a_2 \ldots a_N
attempt: from bisect import bisect_left as bl
  from bisect import bisect_right as br
  from heapq import heappush, heappop, heapify
  import math
  from collections import *
  from functools import reduce, cmp_to_key
  import sys
  
  input = sys.stdin.readline
  
  from itertools import accumulate
  from functools import lru_cache
  
  M = mod = 998244353
  
  
  def factors(n):
      return sorted(
          set(
              reduce(
                  list.__add__,
                  ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0),
              )
          )
      )
  
  
  def inv_mod(n):
      return pow(n, mod - 2, mod)
  
  
  def li():
      return [int(i) for i in input().rstrip("\n").split()]
  
  
  def st():
      return input().rstrip("\n")
  
  
  def val():
      return int(input().rstrip("\n"))
  
  
  def li2():
      return [i for i in input().rstrip("\n")]
  
  
  def li3():
      return [int(i) for i in input().rstrip("\n")]
  
  
  n = val()
  l = li()
  
  
  # @lru_cache(None)
  def dp(l):
      # l = list(l)
  
      ans = float("inf")
      n = len(l)
  
      if n == 1:
          return 0
      ind = 0
      # print(l)
      for i in range(1, n):
          curr = l[i] + l[i - 1]
          if curr < ans:
              ans = curr
              ind = i - 1
  
      return ans + dp(l[:ind] + [ans] + l[ind + 2 :])
  
  
  print(dp(l))
  
problem_description: Statement
  
  There are N slimes lining up in a row. Initially, the i-th slime from the left
  has a size of a_i.
  
  Taro is trying to combine all the slimes into a larger slime. He will perform
  the following operation repeatedly until there is only one slime:
  
    * Choose two adjacent slimes, and combine them into a new slime. The new slime has a size of x + y, where x and y are the sizes of the slimes before combining them. Here, a cost of x + y is incurred. The positional relationship of the slimes does not change while combining slimes.
  
  Find the minimum possible total cost incurred.
samples: [{"input": "4\n    10 20 30 40", "output": "190\n    \n\nTaro should do as follows (slimes being combined are shown in bold):\n\n  * (**10** , **20** , 30, 40) \u2192 (**30** , 30, 40)\n  * (**30** , **30** , 40) \u2192 (**60** , 40)\n  * (**60** , **40**) \u2192 (**100**)\n\n* * *"}, {"input": "5\n    10 10 10 10 10", "output": "120\n    \n\nTaro should do, for example, as follows:\n\n  * (**10** , **10** , 10, 10, 10) \u2192 (**20** , 10, 10, 10)\n  * (20, **10** , **10** , 10) \u2192 (20, **20** , 10)\n  * (20, **20** , **10**) \u2192 (20, **30**)\n  * (**20** , **30**) \u2192 (**50**)\n\n* * *"}, {"input": "3\n    1000000000 1000000000 1000000000", "output": "5000000000\n    \n\nThe answer may not fit into a 32-bit integer type.\n\n* * *"}, {"input": "6\n    7 6 8 6 1 1", "output": "68\n    \n\nTaro should do, for example, as follows:\n\n  * (7, 6, 8, 6, **1** , **1**) \u2192 (7, 6, 8, 6, **2**)\n  * (7, 6, 8, **6** , **2**) \u2192 (7, 6, 8, **8**)\n  * (**7** , **6** , 8, 8) \u2192 (**13** , 8, 8)\n  * (13, **8** , **8**) \u2192 (13, **16**)\n  * (**13** , **16**) \u2192 (**29**)"}]