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: import array as ar
  
  
  def getInt():
      return int(input())
  
  
  def getIntList():
      return [int(x) for x in input().split()]
  
  
  def zeros(n):
      return [0] * n
  
  
  def zeros2(n, m):
      return [zeros(m) for i in range(n)]  # obsoleted zeros((n, m))で代替
  
  
  def getIntLines(n):
      return [int(input()) for i in range(n)]
  
  
  def getIntMat(n, m):  # n行に渡って、1行にm個の整数
      mat = zeros((n, m))
      for i in range(n):
          mat[i] = getIntList()
      return mat
  
  
  class Debug:
      def __init__(self):
          self.debug = True
  
      def off(self):
          self.debug = False
  
      def dmp(self, x, cmt=""):
          if self.debug:
              if cmt != "":
                  print(cmt, ":  ", end="")
              print(x)
          return x
  
  
  def prob_N():  # Grid 1    AC 10  TLE 6
      d = Debug()
      d.off()
      N = getInt()
      A = getIntList()
      d.dmp((N), "N")
      d.dmp((A), "A")
      dp = ar.array("q", [0] * (N - 1))
      for i in range(N - 1):
          dp[i] = A[i] + A[i + 1]
      d.dmp(dp, "dp")
      cost = 0
      for i in range(N - 2):
          mn = min(dp)
          cost += mn
          idx = dp.index(mn)
          # d.dmp((idx,A,dp),'idx,A,dp')
          if idx > 0:
              dp[idx - 1] += A[idx + 1]
          A[idx + 1] += A[idx]
          if idx < len(dp) - 1:
              dp[idx + 1] += A[idx]
          else:
              dp[idx] += A[idx]
          dp.pop(idx)
          A.pop(idx)
          # d.dmp((mn,idx),'mn,idx')
          # d.dmp((A,dp,cost), 'A,dp,cost')
      return cost + dp[0]
  
  
  ans = prob_N()
  if ans is None:
      pass
  elif type(ans) == tuple and ans[0] == 1:  # 1,ans
      for elm in ans[1]:
          print(elm)
  else:
      print(ans)
  
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**)"}]