Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Vasya's Calendar

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya lives in a strange world. The year has *n* months and the *i*-th month has *a*_{i} days. Vasya got a New Year present — the clock that shows not only the time, but also the date.

The clock's face can display any number from 1 to *d*. It is guaranteed that *a*_{i} ≤ *d* for all *i* from 1 to *n*. The clock does not keep information about the current month, so when a new day comes, it simply increases the current day number by one. The clock cannot display number *d* + 1, so after day number *d* it shows day 1 (the current day counter resets). The mechanism of the clock allows you to increase the day number by one manually. When you execute this operation, day *d* is also followed by day 1.

Vasya begins each day checking the day number on the clock. If the day number on the clock does not match the actual day number in the current month, then Vasya manually increases it by one. Vasya is persistent and repeats this operation until the day number on the clock matches the actual number of the current day in the current month.

A year passed and Vasya wonders how many times he manually increased the day number by one, from the first day of the first month to the last day of the *n*-th month inclusive, considering that on the first day of the first month the clock display showed day 1.

Input

The first line contains the single number *d* — the maximum number of the day that Vasya's clock can show (1 ≤ *d* ≤ 10^{6}).

The second line contains a single integer *n* — the number of months in the year (1 ≤ *n* ≤ 2000).

The third line contains *n* space-separated integers: *a*_{i} (1 ≤ *a*_{i} ≤ *d*) — the number of days in each month in the order in which they follow, starting from the first one.

Output

Print a single number — the number of times Vasya manually increased the day number by one throughout the last year.

Examples

Input

4

2

2 2

Output

2

Input

5

3

3 4 3

Output

3

Input

31

12

31 28 31 30 31 30 31 31 30 31 30 31

Output

7

Note

In the first sample the situation is like this:

- Day 1. Month 1. The clock shows 1. Vasya changes nothing.
- Day 2. Month 1. The clock shows 2. Vasya changes nothing.
- Day 1. Month 2. The clock shows 3. Vasya manually increases the day number by 1. After that the clock shows 4. Vasya increases the day number by 1 manually. After that the clock shows 1.
- Day 2. Month 2. The clock shows 2. Vasya changes nothing.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/12/2021 03:56:21 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|