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

1838. 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.

Input

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

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

Sample

inputoutput
5 4
1 2 3 4
4
Problem Author: Denis Dublennykh
Problem Source: Ural Championship 2011