무지개 그릇 구간

원형으로 배치된 그릇 $n$개가 있다.

여러 가지 색의 공이 많이 있다. 색은 $m$가지이며, $i$번째 색의 공은 $c\_i$개 있다.

모든 공을 그릇에 나누어 담아야 한다. 각 색마다 연속된 그릇 $c\_i$개를 골라, 그 범위의 그릇마다 해당 색의 공을 하나씩 넣는다. 연속된 범위는 원형으로 이어진 연속된 그릇들의 집합이다. 서로 다른 색의 범위는 겹쳐도 된다.

그릇 하나에 모든 색의 공이 정확히 하나씩 들어 있으면 그 그릇을 무지개 그릇이라고 한다. 무지개 그릇 구간은 무지개 그릇이 연속으로 이어진 구간 중에서, 다른 무지개 그릇을 덧붙여 더 늘릴 수 없는 구간이다.

공을 배치하여 무지개 그릇 구간의 개수를 최대로 만들어라. $n$과 색별 공의 개수가 주어질 때, 만들 수 있는 무지개 그릇 구간의 최대 개수를 구하라.

첫째 줄에 두 정수 $n$ $(2 \le n \le 10^9)$과 $m$ $(1 \le m \le 10^5)$이 주어진다. 다음 $m$개 줄에는 정수 $c\_i$ $(1 \le c\_i \le n)$가 한 줄에 하나씩 주어진다.

만들 수 있는 무지개 그릇 구간의 최대 개수를 한 줄에 출력한다.