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: from functools import lru_cache
  
  
  def solve(n, aaa):
      @lru_cache(maxsize=None)
      def search_min(li, ri, lc, rc):
          w = ri - li
          if w == 1:
              return 0
          lrc = lc + rc
          if w == 2:
              return aaa[li + 1] * lrc
          if w == 3:
              a1, a2 = aaa[li + 1], aaa[li + 2]
              return (a1 + a2) * lrc + min(a1 * lc, a2 * rc)
          ret = min(
              aaa[i] * lrc + search_min(li, i, lc, lrc) + search_min(i, ri, lrc, rc)
              for i in range(li + 1, ri)
          )
          return ret
  
      return search_min(0, n - 1, 1, 1) + aaa[0] + aaa[-1]
  
  
  n = int(input())
  aaa = list(map(int, input().split()))
  print(solve(n, aaa))
  
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"}]