După ce a adunat bogăţii impresionante din afacerile cu negru de fum, Charles a reuşit să adune un număr proporţional de impresionant de inamici. Iar acum, toate cele $N$ armate ale acestora se află pe drumul către capitala regatului lui Charles, Copşa Mică. Armatele sunt dispuse în şir pe drum, a $i$-a armată de pe drum fiind compusă din $S{~i~}$ soldaţi.

Deoarece Charles însuşi e mai pasionat de Blackjack decât de război, el plănuieşte să îţi împuţineze duşmanii făcându-i să se lupte între ei: la un moment dat el poate unelti ca două armate dispuse *adiacent* pe drum să se lupte între ele. Evident, dintre cele două armate va câştiga cea mai numeroasă, dar va pierde atâţia soldaţi câţi avea armata opozantă. Armata mai puţin numeroasă dispare complet. Mai precis, dacă cele două armate au $A$, respectiv $B$ soldaţi, după bătălie va rămâne o singură armată egală cu diferenţa în modul dintre $A$ şi $B$, $|A-B|$. Dacă armatele au acelaşi număr de soldaţi, ambele dispar.

Deoarece Charles însuşi e mai pasionat de Blackjack decât de război, el plănuieşte să îţi împuţineze duşmanii făcându-i să se lupte între ei: la un moment dat el poate unelti ca două armate dispuse *adiacent* pe drum să se lupte între ele. Evident, dintre cele două armate va câştiga cea mai numeroasă, dar va pierde atâţia soldaţi câţi avea armata opozantă. Armata mai puţin numeroasă dispare complet. Mai precis, dacă cele două armate au $A$, respectiv $B$ soldaţi, după bătălie va rămâne o singură armată egală cu diferenţa în modul dintre $A$ şi $B$, $|A-B|$. Dacă armatele au acelaşi număr de soldaţi, ambele dispar. Charles poate unelti oricâte astfel de lupte.

Charles se întreabă, pentru fiecare interval $[i, j]$ din şirul de armate, care este numărul minim de soldaţi din armatele $i, i+1, ..., j$ care pot rămâne, dacă Charles poate unelti doar lupte între armatele aflate iniţial în intervalul $[i, j]$.