Optimal Guaranteed Score

Farmer John must answer a true/false exam consisting of (N) questions. He has no knowledge of the specific answers but has inside information from Bessie that the total number of questions with answer true is one of (t_1, t_2, \ldots, t_K). Using this information, he wants to answer the questions in such a way that he is guaranteed a high score regardless of which possibility is true.

If Farmer John answers exactly (k) questions as true (and the remaining (N-k) as false), then if the actual number of true answers is (t), his score is at least [ N - \lvert t-k \rvert. ] Bessie’s information tells him that (t) is one of ({t_1, t_2, \ldots, t_K}) (with (0 \le t_i \le N)). Thus, by choosing (k) optimally, his guaranteed score is [ \max_{0\le k\le N};\min_{1\le i\le K};\Bigl(N - \lvert t_i - k \rvert\Bigr). ]

It turns out that if (K > 0), letting (L = \min{t_1, \ldots, t_K}) and (H = \max{t_1, \ldots, t_K}), the best guarantee is achieved by choosing (k) roughly equal to the midpoint between (L) and (H), which yields a guaranteed score of [ N - \left\lceil \frac{H-L}{2} \right\rceil. ] If (K = 0), meaning no extra information is given, then the optimal strategy yields a guaranteed score of [ N - \left\lceil \frac{N}{2} \right\rceil. ] Your task is to compute this optimal guaranteed score for given values of (N) and the possible true counts provided by Bessie.

inputFormat

The input begins with a line containing two integers (N) and (K) (with (1 \le N \le 1{,}000{,}000) and (0 \le K \le 10{,}000)).

If (K > 0), the next (K) lines each contain an integer (t_i) ((0 \le t_i \le N)), representing a possible number of questions with the answer true.

outputFormat

Output a single integer, representing the maximum number of answers that Farmer John is guaranteed to get correct if he uses the optimal strategy.

sample

6 2
0
3

4