分数: 200 点
问题陈述
有 K 蛋糕片。 高桥先生想每天吃一个蛋糕, 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
例如,如果高桥先生按照以下顺序吃蛋糕 2, 1, 2, 3, 1, 3, 1,他可以避免吃与前一天相同类型的蛋糕。
示例输入 2
6 3 1 4 1
示例输出 2
1
有 6 蛋糕。 例如,如果高桥先生吃蛋糕的顺序是 2, 3, 2, 2, 1, 2,他必须吃相同类型的蛋糕(即类型 2)仅在第四天作为前一天。 由于这是最小数,所以答案是 1.
示例输入 3
100 1 100
示例输出 3
99
由于高桥先生只有一种蛋糕,所以从第二天起他只能吃与前一天相同类型的蛋糕。