Score : 600 points
Snuke stands on a number line. He has L ears, and he will walk along the line continuously under the following conditions:
Each time when Snuke passes a point with coordinate i-0.5, where i is an integer, he put a stone in his i-th ear.
After Snuke finishes walking, Ringo will repeat the following operations in some order so that, for each i, Snuke's i-th ear contains A_i stones:
Find the minimum number of operations required when Ringo can freely decide how Snuke walks.
Input is given from Standard Input in the following format:
L A_1 : A_L
Print the minimum number of operations required when Ringo can freely decide how Snuke walks.
4 1 0 2 3
1
Assume that Snuke walks as follows:
Then, Snuke's four ears will contain 0,0,2,3 stones, respectively. Ringo can satisfy the requirement by putting one stone in the first ear.
8 2 0 0 2 1 3 4 1
3
7 314159265 358979323 846264338 327950288 419716939 937510582 0
1