Particle accelerator

import sys 
input_d = sys.stdin.read().split()
n = int(input_d[0])
mass = [int(i) for i in input_d[1:]]


def collide(a,b):
    ma = mass[a]
    mb = mass[b]
    return ma*mb - (min(ma,mb))**2

if n== 1:
    print(0)
    exit()


dic = {}
dp = {}
total_cost = 0
#NO NEED FOR WRAPPING !!
for c in range(n-1):
    for k in range(len(mass)):
        if k ==0:
            right_collision= dic[(mass[0],mass[1])] if dic.get((mass[0],mass[1]),None) is not None else collide(0,1)
            dic[mass[0],mass[1]] = right_collision
            dp[k] = (right_collision,1)
        elif k ==len(mass)-1:
            #if last ele,emnt
            left_collision= dic[(mass[k],mass[k-1])] if dic.get((mass[k],mass[k-1]),None) is not None else collide(k,k-1)
            dic[(mass[k],mass[k-1])] = (left_collision,k-1) #to remove or adapt
            dp[k] = (left_collision,1)
        else :
            left_collision = dic[(mass[k],mass[k-1])] if dic.get(((mass[k],mass[k-1])),None) is not None else collide(k,k-1)
            right_collision= dic[(mass[k],mass[k+1])] if dic.get(((mass[k],mass[k+1])),None)  is not None else collide(k,k+1)
            if left_collision<right_collision:
                dp[k] = (left_collision,k-1)
            else:
                dp[k]= (right_collision,k+1)
    tomerge = min(dp,key=lambda x:dp[x][0])
    total_cost+=dp.get(tomerge)[0]
    tomergewith = dp.get(tomerge)[1]
    mass[tomerge] = mass[tomerge]+ mass[tomergewith]
    mass.pop(tomergewith)
    dp={}


    #now we have dp[i] = (mincosttomerge,index to merge with)
            

print(total_cost)

    

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 13

Verdict: ACCEPTED

Test 14

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 17

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 18

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 19

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 20

Verdict: ACCEPTED

Test 21

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 22

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 23

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 24

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 25

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 26

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 27

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 28

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 29

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 30

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 31

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 32

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 33

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 34

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 35

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 36

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 37

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 38

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 39

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 40

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 41

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 42

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 43

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 44

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 45

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 46

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 47

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 48

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 49

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 50

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 51

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 52

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 53

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 54

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 55

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 56

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 57

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 58

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 59

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 60

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 61

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 62

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 63

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 64

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 65

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 66

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 67

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 68

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 69

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 70

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 71

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 72

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 73

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 74

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 75

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 76

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 77

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 78

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 79

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 80

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 81

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 82

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 83

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 84

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 85

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 86

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 87

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'

Test 88

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 89

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 90

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 39, in <module>
    tomerge = min(dp,key=lambda x:dp[x][0])
TypeError: '<' not supported between instances of 'tuple' and 'int'

Test 91

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "/box/input/code.py", line 35, in <module>
    if left_collision<right_collision:
TypeError: '<' not supported between instances of 'int' and 'tuple'