Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict, deque

dp = defaultdict(lambda: -1)

q = deque([])
q.append((A, 0))

inf = float("inf")

ans = inf
while q:
    t, cost = q.popleft()
    if len(t) == 0:
        ans = min(ans, cost)
        continue

    if len(t) == 1:
        ans = min(ans, cost + t[0])
        continue

    tpl = t
    for i in range(len(tpl) - 1):
        if not (tpl[0:i] + (tpl[i] + tpl[i + 1],) + tpl[i + 2:], tpl[i] + tpl[i + 1]) in q:
            q.append((tpl[0:i] + (tpl[i] + tpl[i + 1],) + tpl[i + 2:], cost + tpl[i] + tpl[i + 1]))

print(ans - sum(A))
exit(0)



Fixed submission:
N = int(input())
A = list(map(int, input().split()))
inf = float("inf")

from itertools import accumulate
Accum = list(accumulate([0] + A))

dp = [ [inf]*(N+1) for _ in range(N+1)]

def dfs(l,r):
    if dp[l][r] != inf:
        return dp[l][r]
    if l == r: 
        return 0
    if l+1 == r: 
        dp[l][r] = A[l]
        return A[l]

    local_ans = inf
    for i in range(l+1, r): # 0 to 4, 0-1, 1-4
        local_ans = min(local_ans, dfs(l,i) + dfs(i,r))
    dp[l][r] = local_ans + Accum[r] - Accum[l]
    return dp[l][r]
print (dfs(0,N)- sum(A))

Buggy python submission (verdict: Runtime Error):
N = int(input())
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict, deque
dp = defaultdict(lambda : -1)

q = deque([])
q.append( (A, 0) )

inf = float("inf")

ans = inf
while q:
    t,cost = q.popleft()
    if len(t) == 0:
        ans = min(ans, cost)
        continue
    
    tpl = t
    for i in range(len(tpl)-1):
        q.append (   ( tpl[0:i] + ( tpl[i]+tpl[i+1], )  + tpl[i+2: ],   tpl[i] + tpl[i+1] ) ) 


print(ans - sum(A))
exit(0)[

def dfs(tpl):
    if dp[tpl] != -1:
        return dp[tpl]
    if len(tpl) == 0:
        return 0
    if len(tpl) == 1:
        dp[tpl] = tpl[0]
        return tpl[0]

    lst_candidates = []
    now_cost = []
    for i in range(len(tpl)-1):
        # print("i: ", i )
        lst_candidates.append (   tpl[0:i] + ( tpl[i]+tpl[i+1], )  + tpl[i+2: ]   )
        now_cost.append ( tpl[i] + tpl[i+1] ) 

    total_cost = []
    for i in range(len(now_cost)):
        total_cost.append ( now_cost [i] + dfs(lst_candidates[i]))

    # print("totla_cost: ", total_cost)
    # print("lst_candidates: ", lst_candidates)
    res = min(total_cost)
    dp[tpl] = res

    return res

# print(dfs(A) - sum(A))


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
inf = float("inf")

from itertools import accumulate
Accum = list(accumulate([0] + A))

dp = [ [inf]*(N+1) for _ in range(N+1)]

def dfs(l,r):
    if dp[l][r] != inf:
        return dp[l][r]
    if l == r: 
        return 0
    if l+1 == r: 
        dp[l][r] = A[l]
        return A[l]

    local_ans = inf
    for i in range(l+1, r): # 0 to 4, 0-1, 1-4
        local_ans = min(local_ans, dfs(l,i) + dfs(i,r))
    dp[l][r] = local_ans + Accum[r] - Accum[l]
    return dp[l][r]
print (dfs(0,N)- sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict
dp = defaultdict(lambda : -1)

def dfs(tpl):
    if dp[tpl] != -1:
        return dp[tpl]
    if len(tpl) == 0:
        return 0
    if len(tpl) == 1:
        dp[tpl] = tpl[0]
        return tpl[0]

    lst_candidates = []
    now_cost = []
    for i in range(len(tpl)-1):
        # print("i: ", i )
        lst_candidates.append (   tpl[0:i] + ( tpl[i]+tpl[i+1], )  + tpl[i+2: ]   )
        now_cost.append ( tpl[i] + tpl[i+1] ) 

    total_cost = []
    for i in range(len(now_cost)):
        total_cost.append ( now_cost [i] + dfs(lst_candidates[i]))

    # print("totla_cost: ", total_cost)
    # print("lst_candidates: ", lst_candidates)
    res = min(total_cost)
    dp[tpl] = res

    return res

print(dfs(A) - sum(A))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
inf = float("inf")

from itertools import accumulate
Accum = list(accumulate([0] + A))

dp = [ [inf]*(N+1) for _ in range(N+1)]

def dfs(l,r):
    if dp[l][r] != inf:
        return dp[l][r]
    if l == r: 
        return 0
    if l+1 == r: 
        dp[l][r] = A[l]
        return A[l]

    local_ans = inf
    for i in range(l+1, r): # 0 to 4, 0-1, 1-4
        local_ans = min(local_ans, dfs(l,i) + dfs(i,r))
    dp[l][r] = local_ans + Accum[r] - Accum[l]
    return dp[l][r]
print (dfs(0,N)- sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
# A = list(map(int, input()))
A = tuple(map(int, input().split()))

from collections import defaultdict
dp = defaultdict(lambda : -1)

def dfs(tpl):
    if dp[tpl] != -1:
        return dp[tpl]
    if len(tpl) == 0:
        return 0
    if len(tpl) == 1:
        dp[tpl] = tpl[0]
        return tpl[0]

    lst_candidates = []
    now_cost = []
    for i in range(len(tpl)-1):
        # print("i: ", i )
        lst_candidates.append (   tpl[0:i] + ( tpl[i]+tpl[i+1], )  + tpl[i+2: ]   )
        now_cost.append ( tpl[i] + tpl[i+1] ) 

    total_cost = []
    for i in range(len(now_cost)):
        total_cost.append ( now_cost [i] + dfs(lst_candidates[i]))

    # print("totla_cost: ", total_cost)
    # print("lst_candidates: ", lst_candidates)
    res = min(total_cost)
    dp[tpl] = res

    return res

print(dfs(A) - sum(A))


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
inf = float("inf")

from itertools import accumulate
Accum = list(accumulate([0] + A))

dp = [ [inf]*(N+1) for _ in range(N+1)]

def dfs(l,r):
    if dp[l][r] != inf:
        return dp[l][r]
    if l == r: 
        return 0
    if l+1 == r: 
        dp[l][r] = A[l]
        return A[l]

    local_ans = inf
    for i in range(l+1, r): # 0 to 4, 0-1, 1-4
        local_ans = min(local_ans, dfs(l,i) + dfs(i,r))
    dp[l][r] = local_ans + Accum[r] - Accum[l]
    return dp[l][r]
print (dfs(0,N)- sum(A))