19130번 - Long Binary Sequence 다국어

문제

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

Now bobo would like to know the number of distinct consecutive substrings of $s$.

입력

The first line contains 2ドル$ integers $n, 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$).

출력

A single integer denotes the number of distinct substrings.

제한

힌트