你有 $n$ 个碗，排成一个圆圈。 你有许多不同颜色的球。共有 $m$ 种不同的颜色，其中第 $i$ 种颜色的球有 $c_i$ 个。 你需要将所有的球分配到碗中。为此，对于每种颜色，你需要选择一个大小为 $c_i$ 的连续碗的范围，并在该范围内的每个碗中放入一个该颜色的球。碗的连续范围是指圆圈上连续的一组碗。不同颜色的范围允许重叠。 如果一个碗中包含每种颜色各一个球，则称该碗为“彩虹碗”。“彩虹碗范围”是指一组连续的彩虹碗，且无法通过包含另一个彩虹碗来扩展。 你希望安排球在碗中的位置，以最大化彩虹碗范围的数量。 给定碗的数量和每种颜色的球的数量，求最多能形成多少个彩虹碗范围？

输入格式

第一行包含两个整数 $n$ ($2 \le n \le 10^9$) 和 $m$ ($1 \le m \le 10^5$)。 接下来的 $m$ 行，每行包含一个整数 $c_i$ ($1 \le c_i \le n$)。

输出格式

输出一个整数，表示最多能形成的彩虹碗范围的数量。

样例

样例输入 1

4 2
3
3

样例输出 1

2

样例输入 2

10 11
3
1
4
1
5
9
2
6
5
3
5

样例输出 2

1