Long Binary Sequence

Time limit2sMemory limit512 MB

Summary

Count the distinct consecutive substrings of a binary string of length up to 1e9, where the 1s are given at m up to 1000 positions.

Level: Hard9 of 10
Topics: String matching, String, Implementation
Solved: No attempts yet

Problem

Bobo has a very long binary sequence $s$ of length $n$ . All positions are $0$ except for $m$ positions $x_1, x_2, \dots, x_m$ , and $s_{x_1} = s_{x_2} = \dots = s_{x_m} = 1$ .

Find the number of distinct consecutive substrings of $s$ .

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n \leq 10^9$ , $1 \leq m \leq \min\{n, 1000\}$ ).

The second line contains $m$ integers $x_1, x_2, \dots, x_m$ ( $1 \leq x_1 < x_2 < \dots < x_m \leq n$ ).

Output

Print a single integer, the number of distinct consecutive substrings of $s$ .

Examples2

Example 1
Input
```
3 2
1 3
```
Expected output
```
5
```
Example 2
Input
```
1000000000 1
1
```
Expected output
```
1999999999
```