Cerința

Se dă numărul natural n și un șir de n numere naturale. Determinați numărul minim de operații necesare pentru a face șirul palindromic. Singura operație admisă este înlocuirea a două elemente adiacente cu un element care conține suma lor.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul minim de operații pentru a transforma șirul dat într-un șir palindromic.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• elementele șirului dat vor fi mai mici decât 10.000
• un șir este palindromic dacă se citește la fel în ambele sensuri

Exemplu:

Intrare

4
1 4 5 1

Ieșire

1

Explicație

Se adună 4 cu 5 și șirul devine 1 9 1