Problem Description

There are $ K $ cakes. Takahashi plans to eat one of these cakes each day for $ K $ days.

There are $ T $ types of cakes, and there are $ a_i $ cakes of type $i\ (1≦i≦T)$.

Takahashi will get bored if he eats the same type of cake two days in a row. Therefore, he wants to determine the order in which he eats the cakes to minimize the number of days he eats the same type of cake as the previous day.

Please find the minimum number of days Takahashi eats the same type of cake as the previous day for him.

Input Format

The input is given from the standard input in the following format:

$ K $ $ T $ $ a_1 $ $ a_2 $ $ ... $ $ a_T $

Output Format

Output the minimum number of days Takahashi eats the same type of cake as the previous day.

Sample Input and Output

Sample Input #1

7 3
3 2 2

Sample Output #1

0

Sample Input #2

6 3
1 4 1

Sample Output #2

1

Sample Input #3

100 1
100

Sample Output #3

99

Notes/Hints

Constraints

• $1≦K≦10000,\ 1≦T≦100$
• $ 1≦a_i≦100 $
• $ a_1+a_2+ $...$+a_T\ =\ K$

Sample Explanation 1

There are $ 7 $ cakes. For example, if he eats them in the order of type $ 2,1,2,3,1,3,1 $, he can avoid eating the same type of cake as the previous day.

Sample Explanation 2

There are $ 6 $ cakes. If he eats them in the order of type $ 2,3,2,2,1,2 $, he will only eat the same type of cake as the previous day on the 4th day, which is the minimum. Therefore, the answer is $ 1 $.

Sample Explanation 3

Since Takahashi only has one type of cake, he has no choice but to eat the same type of cake as the previous day from the 2nd day onwards.

见题面 Input 部分

见题面 Output 部分