output_description: Print the minimum possible sum of the integers written on the last two cards
  remaining.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 ... A_N
attempt: import sys
  
  MAX_INT = int(10e9)
  MIN_INT = -MAX_INT
  mod = 1000000007
  sys.setrecursionlimit(1000000000)
  
  
  def IL():
      return list(map(int, input().split()))
  
  
  def SL():
      return input().split()
  
  
  def I():
      return int(sys.stdin.readline())
  
  
  def S():
      return input()
  
  
  def tami(visited, x, cnt, List):
      global ans
      # print(a)
      # print("visited=",visited)
      # print("List=",List)
      # print("-----------")
      if cnt == N - 2:
          ans = min(ans, List[0] + List[-1])
          return
      else:
          for j in range(1, N - 1):  # 次の探索 j
              if j in visited:
                  continue
              else:
                  if x < j:
                      for v in range(x + 1, j):  # x→j 間に未探索 → ダメ
                          if v not in visited:
                              break
                      else:
                          for k in range(j - 1, -1, -1):  # listの更新
                              if k not in visited:
                                  left = k
                                  break
                          for k in range(j + 1, N):
                              if k not in visited:
                                  right = k
                                  break
                          l = (
                              List[:left]
                              + [List[left] + List[j]]
                              + List[left + 1 : right]
                              + [List[right] + List[j]]
                              + List[right + 1 :]
                          )
                          tami(visited + [j], j, cnt + 1, l)
                  else:
                      for k in range(j - 1, -1, -1):  # listの更新
                          if k not in visited:
                              left = k
                              break
                      for k in range(j + 1, N):
                          if k not in visited:
                              right = k
                              break
                      l = (
                          List[:left]
                          + [List[left] + List[j]]
                          + List[left + 1 : right]
                          + [List[right] + List[j]]
                          + List[right + 1 :]
                      )
                      tami(visited + [j], j, cnt + 1, l)
  
  
  N = I()
  a = IL()
  
  ans = MAX_INT
  for i in range(1, N - 1):
      l = a[: i - 1] + [a[i - 1] + a[i]] + [a[i]] + [a[i + 1] + a[i]] + a[i + 2 :]
      # print(l)
      tami([i], i, 1, l)
  
  print(ans)
  
problem_description: Statement
  
  There is a stack of N cards, each of which has a non-negative integer written
  on it. The integer written on the i-th card from the top is A_i.
  
  Snuke will repeat the following operation until two cards remain:
  
    * Choose three consecutive cards from the stack.
    * Eat the middle card of the three.
    * For each of the other two cards, replace the integer written on it by the sum of that integer and the integer written on the card eaten.
    * Return the two cards to the original position in the stack, without swapping them.
  
  Find the minimum possible sum of the integers written on the last two cards
  remaining.
samples: [{"input": "4\n    3 1 4 2", "output": "16\n    \n\nWe can minimize the sum of the integers written on the last two cards\nremaining by doing as follows:\n\n  * Initially, the integers written on the cards are 3, 1, 4, and 2 from top to bottom.\n  * Choose the first, second, and third card from the top. Eat the second card with 1 written on it, add 1 to each of the other two cards, and return them to the original position in the stack. The integers written on the cards are now 4, 5, and 2 from top to bottom.\n  * Choose the first, second, and third card from the top. Eat the second card with 5 written on it, add 5 to each of the other two cards, and return them to the original position in the stack. The integers written on the cards are now 9 and 7 from top to bottom.\n  * The sum of the integers written on the last two cards remaining is 16.\n\n* * *"}, {"input": "6\n    5 2 4 1 6 9", "output": "51\n    \n\n* * *"}, {"input": "10\n    3 1 4 1 5 9 2 6 5 3", "output": "115"}]