Mock CCC '18 Contest 5 S4 - Carol's Cute Conquest

View as PDF

Submit solution


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

Author:
Problem type

Carol thought she was done with the CCC, but the CCC wasn't done with her.

Having arrived at Google, Carol realized that the scale at which she was thinking was way too small. What would happen if she had to consider strings with millions of letters?

The CCC, recognizing this opportunity, struck. They sent her an email containing many occurrences of the letter C.

Carol realized that, in order for her to be truly free of the CCC, she would have to be okay with just how much the CCC controlled around her. She decided to count the number of substrings of the email that have CCC as a subsequence.

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. The email is a string of N characters, with exactly K of them being C.

Each of the next K lines contains a single integer, a_i, indicating that character a_i of the email is C.

Output Specification

Output a single integer, the number of substrings that contain CCC as a subsequence.

Sample Input

5 4
1
2
4
5

Sample Output

3

Comments

There are no comments at the moment.