Given a binary string of length $N$, where exactly $K$ characters are ones, compute the number of substrings that have at least three ones.

Constraints

$1\le N\le {10}^9$

$0\le K\le {10}^6$

$1\le a_i\le N$

$a_i$ are presented in sorted order.

$K\le N$

In tests worth $5$ marks, you may assume $K\le {10}^2$.

In tests worth an additional $5$ marks, you may assume $K\le {10}^5$.

Input Specification

The first line of the input contains two space-separated integers, $N$ and $K$.

Each of the next $K$ lines contains a single integer, $a_i$, indicating that character $a_i$ of the string is a one.

Output Specification

Output a single integer, the number of substrings that contain at least three ones.

Sample Input

5 4
1
2
4
5

Sample Output

3