Somme di sequenze

Data una sequenza S di N numeri interi, tipo 11 -4 52 -7 -2 -20, vogliamo computare la somma di tutti i numeri in S avvalendoci di un robot con capacità limitate. Infatti, tale robot può soltanto effettuare la somma intermedia Y di due numeri A e B consecutivi nella sequenza, rimpiazzando A e B con Y e ottenendo così una sequenza più corta (con un intero in meno).

Per effettuare tale somma intermedia Y e produrre la sequenza più corta, il robot consuma esattamente |Y| unità di energia (dove |Y|indica il valore assoluto di un numero intero Y).

Per calcolare la somma degli N numeri in S sono quindi necessarie N-1 somme intermedie. Pur disponendo di energia sufficiente per eseguire le N-1 somme intermedie in tale calcolo, il robot ha problemi con i picchi di energia. In altre parole, vogliamo che il massimo consumo energetico per una somma intermedia (il picco energetico) sia minimizzato.
sequenze
Nel caso di cui sopra una soluzione ottima è data da

11 -4 52 -7 (-2 -20)
11 -4 52 (-7 –22)
11 -4 (52 -29)
(11 -4) 23
(7 23)
30

In questo caso i valori intermedi ottenuti sono -22, -29, 23, 7, 30 e il picco energetico è 30, essendo il massimo tra |-22|, |-29|, |23|, |7|e |30|.
Meglio di così non si può fare in quanto il valore della somma è 30.

Un altro esempio è dato dalla sequenza

(7 -1) -8
(6 -8)
-2

in cui le somme intermedie hanno generato 6 e -2 e quindi il picco energetico è pari a 6. Tale picco è minimo poiché l’altra possibilità consiste nel sommare prima -1 con -8 e poi 7 con -9, dando luogo a un picco pari a 9.

Scrivete un programma che calcoli il minimo picco energetico per una sequenza di interi.

Dati in Input

Il file input.txt è composto da due righe.

• La prima riga contiene un intero positivo che rappresenta il numero N di interi nella sequenza d’ingresso.
• La successiva riga contiene N interi, separati da uno spazio, che rappresentano la sequenza su cui computare la somma.

 

Dati in Output

Il file output.txt è composto da una sola riga che contiene l’intero non negativo E, il quale rappresenta il picco energetico minimo del robot per calcolare la somma degli interi nella sequenza d’ingresso.

Assunzioni

• 2 ≤ N ≤ 500

Esempi