/ 
Time Limit: 1 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
K 個のケーキがあります。高橋君は、1日に一つずつ、K 日かけてこれらのケーキを食べようと考えています。
ケーキはT 種類あり、種類i (1≦i≦T) のケーキはa_i 個あります。
二日連続で同じ種類のケーキを食べると飽きてしまうため、高橋君は、うまくケーキを食べる順番を決めて、前日と同じ種類のケーキを食べる日数を最小にしようと考えました。
高橋君のために前日と同じ種類のケーキを食べる日数の最小値を求めてください。
制約
- 1≦K≦10000, 1≦T≦100
- 1≦a_i≦100
- a_1+a_2+ ... +a_T = K
入力
入力は以下の形式で標準入力から与えられる。
K T a_1 a_2 ... a_T
出力
前日と同じ種類のケーキを食べる日数の最小値を出力せよ。
入力例 1
7 3 3 2 2
出力例 1
0
ケーキは7個あります。例えば種類2,1,2,3,1,3,1の順で食べると一度も前日と同じ種類のケーキを食べなくてすみます。
入力例 2
6 3 1 4 1
出力例 2
1
ケーキは6個あります。種類2,3,2,2,1,2の順で食べると4日目だけ前日と同じ種類2のケーキを食べることになり、これが最小になるので答えは1です。
入力例 3
100 1 100
出力例 3
99
高橋君は一種類のケーキしか持っていないため、2日目以降は毎日前日と同じ種類のケーキを食べるしかありません。
Score : 200 points
Problem Statement
There are K pieces of cakes. Mr. Takahashi would like to eat one cake per day, taking K days to eat them all.
There are T types of cake, and the number of the cakes of type i (1 ≤ i ≤ T) is a_i.
Eating the same type of cake two days in a row would be no fun, so Mr. Takahashi would like to decide the order for eating cakes that minimizes the number of days on which he has to eat the same type of cake as the day before.
Compute the minimum number of days on which the same type of cake as the previous day will be eaten.
Constraints
- 1 ≤ K ≤ 10000
- 1 ≤ T ≤ 100
- 1 ≤ a_i ≤ 100
- a_1 + a_2 + ... + a_T = K
Input
The input is given from Standard Input in the following format:
K T a_1 a_2 ... a_T
Output
Print the minimum number of days on which the same type of cake as the previous day will be eaten.
Sample Input 1
7 3 3 2 2
Sample Output 1
0
For example, if Mr. Takahashi eats cakes in the order of 2, 1, 2, 3, 1, 3, 1, he can avoid eating the same type of cake as the previous day.
Sample Input 2
6 3 1 4 1
Sample Output 2
1
There are 6 cakes. For example, if Mr. Takahashi eats cakes in the order of 2, 3, 2, 2, 1, 2, he has to eat the same type of cake (i.e., type 2) as the previous day only on the fourth day. Since this is the minimum number, the answer is 1.
Sample Input 3
100 1 100
Sample Output 3
99
Since Mr. Takahashi has only one type of cake, he has no choice but to eat the same type of cake as the previous day from the second day and after.