Mock CCC '18 Contest 5 S4 - Sparse Binary String Counting

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

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

Comments

There are no comments at the moment.