Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
1s, 512 MB

Arithmetic Sequence is a sequence of numbers where the difference between two consecutive numbers are same. For example, the sequence 2, 4, 6, 8, 10, .... n is an arithmetic sequence where the difference between consecutive numbers is 2.

Carl Friedrich Gauss is known to be one of the best mathematician of all time. A story about his childhood goes like this: When Gauss was nine years old, his teacher asked him to add numbers from 1 to 100, thinking it would keep Gauss busy for a while. But Gauss came up with the answer very quickly instead. He found the following observation very helpful while solving the problem:

1 + 2 + 3 + 4 + 5 + ...... + 100

100 + 99 + 98 + 97 + 96 + ........+ 1

101 + 101 + 101 + 101 + 101 + ....... + 101

Since there are 100 terms each having the value of 101, the answer should be ( 100 * 101 ) / 2, because each number from 1 to 100 were added twice in this summation. So, if a person is given n, he can easily calculate the sum from 1 to n with a simple formula.

In this problem, you will be given an integer **N**, you will have to find the summation of integers from 1 to **N**. To make a the problem a bit more challenging, you will also be asked to subtract some of the numbers from this summation.

The first line contain an integer **N** **( 1 ≤ N ≤ 109 )**, the length of the arithmetic sequence. The next line will contain an integer **M** **( 1 ≤ M ≤ min( N , 1000000 ) )**, the amount of number that will be subtracted from the sequence. The following **M** lines will have one integer **Mi** **(1 ≤ Mi ≤ N)**, the numbers that will be subtracted from the sequence. Each of these **M** numbers will be **unique**.

Output a single integer, the result of the arithmetic sequence after subtracting the given numbers.

Input | Output |
---|---|

3 1 3 | 3 |

Input | Output |
---|---|

3 2 1 2 | 3 |

94% Solution Ratio

subintra2016.8$8KpTbEarliest,

habib036Fastest, 0.0s

subintra2016.8$8KpTbLightest, 131 kB

joe.masterShortest, 80B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.