ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Samurai's Stroke

Time limit: 0.5 second
Memory limit: 64 MB
Kogan-sensei continues teaching young Gennosuke Fujiki the art of sword fighting. Kogan fixes a thin bamboo stem of length l horizontally on n props and orders Gennosuke to cut it into two pieces. Kogan says that a samurai's sword must be as sharp and the stroke must be as fast that both pieces of the stem don't move after the stroke.
Gennosuke has noticed that not only samurai mastery is important but also the place where the sword cuts the stem. If the center of mass of a stem piece is not located between two props, the piece will fall. Gennosuke wants to paint some parts of the bamboo stem white so that if he cuts the stem at a white point at least one of the resulting pieces will fall. Help him calculate the total length of the stem parts he will have to paint.


The first line contains the integers l and n (3 ≤ l ≤ 109; 2 ≤ n ≤ 105). In the second line you are given n integers smaller than l. They are the distances from the left end of the bamboo stem to the supporting props given in the ascending order. It is guaranteed that the initial position of the stem is stable.


Output the total length of segments of the stem that Gennosuke should paint white. The answer should be rounded up to the nearest integer.


5 4
1 2 3 4
Problem Author: Denis Dublennykh
Problem Source: Ural Championship 2011
To submit the solution for this problem go to the Problem set: 1838. Samurai's Stroke