402060: GYM100637 F The Pool for Lucky Ones

A new swimming pool has been built in Kazan for the forthcoming Water Sports World Championship. The pool has N lanes. Some of the lanes are already occupied by swimmers. Tatar scientists have divided the lanes into the lucky and unlucky ones. The unlucky lanes are those with the maximum amount of swimmers. That is, there is no other lane where there would be more swimmers than on unlucky one. The unlucky lanes make swimmers unhappy. The rest of the lanes are considered to be lucky. The lucky lanes make people happy. The scientists took a decision to make more people happy. In order to do this they had an agreement with the pool manager saying they can move a single person from any lane to the one neighboring if it was necessary. The swimmer from the first lane can only be moved to the second lane, and the swimmer from the last lane –– to the one before last.

The first line contains an integer N — the amount of lanes in the pool (3 ≤ N ≤ 10⁵). The second line contains N integers p_i separated with spaces, describing distribution of swimmers between the lanes where p_i is the amount of swimmers on i-th lane (0 ≤ p_i ≤ 10⁵).

Output a single number — minimal possible number of unhappy swimmers.

3
1 3 5

5

4
1 0 1 0

2