Problem J
Rainbow Bowl Ranges

You have a set of $n$ bowls, arranged in a circle.

You have many balls of various colors. There are $m$ different colors, and you have $c_i$ balls of the $i^\texttt {th}$ color.

You want to distribute all the balls into the bowls. To do this, for each color, you choose a contiguous range of bowls of size $c_i$ and place one ball of that color in each bowl in the range. A contiguous range of bowls is a set of consecutive bowls around the circle. Ranges from different colors are allowed to overlap.

A bowl is rainbow if it contains one ball of each color. A rainbow bowl range is a contiguous range of rainbow bowls that cannot be extended by including another rainbow bowl.

You want to arrange balls in bowls to maximize the number of rainbow ranges.

Given the number of bowls and the number of balls of each color, what is the maximum number of rainbow bowl ranges that can be formed?

Input

The first line contains two integers, $n$ $(2 \le n \le 10^9)$, $m$ $(1 \le m \le 10^5)$.

The next $m$ lines each contain a single integer, $c_i$ $(1 \le c_i \le n)$.

Output

Print a single integer, the maximum number of rainbow bowl ranges that can be formed.

4 2
3
3

2

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

1