Vasya lives in a strange world. The year has n months and the i-th month has ai days.…
- User
Vasya lives in a strange world. The year has n months and the i-th month has ai 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 ai ≤ 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 ≤ 106).
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: ai (1 ≤ ai ≤ 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.
In total, Vasya manually changed the day number by 1 exactly 2 times.
Assistant
We need to compute total number of manual increments Vasya does over a year of n months, with month i having a_i days. The clock can display numbers from 1 to d. It initially shows 1 on day 1 of month 1. At the start of each day (i.e., before any manual adjustment that day), Vasya checks the displayed number against the actual day number (which ranges from 1 to a_i for that month). If they don't match, he repeatedly increments manually (by one, with wrap-around from d to 1) until they match. So for each day, the number of manual increments is the number of steps needed to go from the clock's current display (at the start of the day, before adjustments) to the target day number, modulo d. However, note that after he finishes adjusting, the clock shows the correct day number. Then overnight, presumably the clock increments automatically? Let's read: "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)." That's the automatic behavior at the transition to the next day. So after the day ends, the clock automatically increments (with wrap) to the next day's number. Then Vasya checks that number in the morning. So the sequence: Start day 1 month 1: clock shows 1 (initial). Then Vasya checks: matches actual day 1, so no manual increments. At the end of day, clock automatically increments to next day number: becomes 2 (since 1+1=2 ≤ d). Day 2 month 1: clock shows 2. Check: matches actual day 2, no manual increments. At end of day, increments to 3. But now, after month 1 ends (which had 2 days), next day is day 1 of month 2. So at end of day 2 of month 1, clock increments to 3. Then morning of day 1 month 2: clock shows 3. Actual day is 1. So they don't match. Vasya manually increments until it shows 1. He increments: from 3 to 4 (1), from 4 to 1 (wrap: 4→5? Wait d=4 in example: after 4 comes 1. So increments: 3→4 (1 step), 4→1 (1 step). So 2 manual increments. After that, clock shows 1. At end of day, it increments automatically to 2. Next day (day 2 month 2) clock shows 2, matches. So total increments = 2.
Thus, we need to compute the total manual increments over all days.
We can simulate day by day: keep current display value (before checking). Initially cur = 1. For each day i (in order of months and days), let target = day number within month (1..a_i). If cur != target, we need to compute the number of increments needed to go from cur to target with wrap-around: it's (target - cur) mod d, but careful: we increment until we reach target; each increment increases cur by 1 modulo d (with 1 after d). The number of increments needed is ( (target - cur + d) % d ). But is that correct? Suppose cur = 5, target = 1, d = 10. increments: 5->6,7,8,9,10,1: that's 6 increments? Actually (1-5+10)%10 = 6%10=6. Yes. So the number of manual increments = (target - cur + d) % d. However, if cur == target, it's 0. After manual adjustments, cur becomes target. Then at the end of the day, the clock auto increments: cur = (target % d) + 1? Actually, after the day, the clock increments automatically to next day. But careful: The problem statement: "when a new day comes, it simply increases the current day number by one." It seems the increment happens at the start of the new day? Or at the transition? The description: "Vasya begins each day checking the day number on the clock. If ... Vasya manually increases it by one ... 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." Then: "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." It doesn't explicitly describe the automatic increment happening at midnight. But from the example: after day 2 month1, the clock became 3 on the next morning. That must be due to automatic increment. So we can model as: at the end of each day, after Vasya has adjusted (if any), the clock automatically increments by one (with wrap) to prepare for the next day. However, note that on the last day of the year, after checking and possibly adjusting, do we care about the auto increment? The problem counts manual increments from first day to last day inclusive. So we don't need to consider any auto increment after last day. So we can just simulate: start with cur = 1. For each day (in chronological order), let target = current day of month. If cur != target, add increments = (target - cur + d) % d. Then set cur = target. Then, if this is not the last day overall, do auto increment: cur = (cur % d) + 1? Actually cur is between 1 and d. So cur = (cur == d) ? 1 : cur+1. Then proceed to next day. But careful: The auto increment occurs after the day, so for the next day, the starting cur is that incremented value.
But is there any nuance about the automatic increment when the clock is manually adjusted? The manual adjustments also increment the display. They are separate. The auto increment is a separate mechanism that happens each day (maybe at midnight). In the example, after manual adjustments on day 1 month 2, cur became 1. Then after that day ends, auto increment makes it 2 for the next day. So our simulation matches.
Thus total manual increments = sum over days of ((target - cur_pre + d) mod d), where cur_pre is the display at start of day.
We can compute this iteratively. d up to 1e6, n up to 2000, total days up to sum a_i, which could be large because a_i ≤ d = 1e6, n up to 2000, so sum up to 2e9 maybe? That's too large for day-by-day simulation. Need a smarter method.
We need to compute total increments efficiently without iterating over each day individually, because days could be huge.
Observation: The process is deterministic and can be computed in terms of the sequence of target values. Let's denote the days in order as a list of numbers: for month i, we have days 1,2,...,a_i. So the target sequence is: 1,2,...,a1, then 1,2,...,a2, ..., 1,...,an. The total number of days is N = sum_i a_i. We have cur initially 1. Then for each day t, let target = T[t]. We compute inc[t] = (T[t] - cur + d) % d (if non-zero, but zero otherwise). Then cur becomes T[t] after manual adjustments, then auto increment to cur_next = (T[t] mod d) + 1? Actually auto: after day, cur = T[t] + 1, but wrap if > d. So cur_next = (T[t] % d) + 1, or more precisely: if T[t] == d, then cur_next = 1; else cur_next = T[t] + 1.
Thus we can think of the state transition from day to day: at the start of day t, we have a value cur. After the day, we have cur_next = (T[t] + 1) mod d with 1-based? Actually, if T[t] = d, then +1 = d+1, which becomes 1. So yes: cur_next = ((T[t]) % d) + 1, but since T[t] in [1,d], we can compute: cur_next = T[t] + 1 if T[t] < d else 1.
But note: after manual adjustments, cur becomes T[t]. So the auto increment is exactly +1 mod d from that. So cur_next = (T[t] + 1) if T[t] < d, else 1.
Thus, we can compute the start cur for day t+1 as cur_{t+1} = (T[t] + 1) mod d (with mapping d+1→1). And we also have inc[t] = (T[t] - cur_t + d) % d.
So we can compute total increments as sum over t of (T[t] - cur_t mod d) where we treat the difference in the cyclic sense from cur_t to T[t] forward. Because (T[t] - cur_t + d) % d is the forward distance.
Now cur_t evolves deterministically based on previous T's. So essentially we have:
cur_1 = 1 (start of first day).
For t from 1 to N: inc_t = (T[t] - cur_t) mod d (0..d-1, but if it's 0 then 0) cur_{t+1} = (T[t] + 1) mod d (with 1..d representation)
So total manual increments = sum inc_t.
We need to compute sum efficiently given T[t] is a repetitive pattern: for each month, T runs 1,2,...,a_i.
But note: a_i can be less than d. Also d can be large.
We can think of cur as a number that evolves. Since N may be huge (up to 2e9), we need to compute total sum without iterating over each day.
Observation: The process is similar to a clock that resets after d. The manual increments adjust the clock to match the target day. The auto increment is like the clock's natural progression (but it always increments by 1 each day, regardless of month lengths). Actually, the auto increment is exactly what a normal day counter would do if it always increased by 1 each day, wrapping after d. So essentially, the clock's natural behavior (without manual adjustments) would be to display a sequence that increments by 1 each day (with wrap). Vasya manually adjusts it to match the actual day number (which is based on months). So the number of manual increments is essentially the total number of times Vasya has to "correct" the clock to match the desired date, given that the clock is otherwise just a free-running counter.
We can think of it like this: Imagine the clock's display (if never manually adjusted) would simply be a counter that starts at 1 and increments each day modulo d. But Vasya resets it (by advancing manually) to the correct date each morning. However, the manual adjustment is done by incrementing until it matches; that is effectively "setting" the clock to the correct value by fast-forwarding. After that, the clock continues its auto increment. So the number of manual increments on a day is the number of steps needed to catch up from the current display (which is the result of previous auto increments plus previous manual adjustments) to the target. This is essentially the difference modulo d.
If we consider the ideal clock that would be correct without adjustments, that would be the actual date values T[t]. But the actual clock runs on its own logic. The total manual increments can be computed as the sum of "gaps" between the free-running clock's value and the target, measured in forward steps.
Alternatively, define C_t as the display value at the start of day t (before manual adjustments). Then C_1 = 1. And after day t, the display becomes T[t] (after manual) then auto increments to C_{t+1} = (T[t] + 1) mod d. So we have C_{t+1} = (T[t] + 1) mod d. Also note that T[t] is known. So C_t can be expressed in terms of previous T's. Specifically, C_t = (T[t-1] + 1) mod d for t>1.
Thus we can compute inc_t = (T[t] - C_t) mod d.
But also note that if we compute inc_t as the forward distance, that is (T[t] - C_t + d) % d.
Now total inc = Σ_t (T[t] - C_t + d) % d.
Given that both T[t] and C_t are between 1 and d, but mod operations needed.
But perhaps we can derive a simpler formula. Let's examine the example:
Input 2: d=5, n=3, a=[3,4,3]. So days: month1: 1,2,3; month2: 1,2,3,4; month3:1,2,3. Let's simulate quickly:
Start C1=1, T1=1 => inc=0, after: C2 = (1+1)=2. Day2: C2=2, T2=2 => inc=0, C3=3. Day3: C3=3, T3=3 => inc=0, C4= (3+1)=4. Day4 (month2 day1): C4=4, T4=1 => inc = (1-4+5)%5=2%5=2? Actually (1-4+5)=2, inc=2. So inc=2. After adjust to 1, then auto: C5 = (1+1)=2. Day5: C5=2, T5=2 => inc=0, C6=3. Day6: C6=3, T6=3 => inc=0, C7=4. Day7: C7=4, T7=4 => inc=0, C8 = (4+1)=5? Since d=5, 4+1=5 -> C8=5. Day8 (month3 day1): C8=5, T8=1 => inc = (1-5+5)%5=1%5=1? Actually (1-5+5)=1, inc=1. Then C9 = (1+1)=2. Day9: C9=2, T9=2 => inc=0, C10=3. Day10: C10=3, T10=3 => inc=0. Total inc=2+1=3. Matches sample.
Now, note that inc_t = 0 when C_t = T[t]; otherwise positive. How often does that happen? The clock's auto progression increments by 1 each day, while the target progression resets to 1 at month boundaries, and increases each day within month until a_i. So the only times when C_t differs from T[t] are when a month ends and we start a new month: because after the end of a month, the auto increment would have gone from the last day number (a_i) to a_i+1 (or wrap). But the next day's target is 1 (if a_i < d, the auto increment might be a_i+1, which is likely not 1 unless a_i = d). Actually more generally, the auto increment after day with target T is T+1 mod d; the next target is either T+1 (if we are within the same month and T+1 ≤ a_i) or 1 (if we are at month end). So within a month, if the month's days are consecutive and we have not reached the month's end, the target T[t] equals the previous target T[t-1]+1 (until the last day of the month). The clock's auto increment also gives C_t = T[t-1] + 1 (since after previous day, it auto increments from T[t-1] to T[t-1]+1, mod d). So within a month, as long as we haven't hit a wrap issue, we have C_t = T[t] because T[t] = T[t-1]+1 (provided that T[t-1]+1 ≤ a_i, and also that T[t-1] < d, and no wrap). However, if d is smaller than a_i? But it's guaranteed a_i ≤ d. So T[t-1] ≤ a_i ≤ d, so T[t-1] < d unless it's exactly d. If T[t-1] = d, then auto increment gives 1. But can T[t-1] = d? Since a_i ≤ d, it's possible if a_i = d. In a month with d days, the last day is d. Then auto increment from d gives 1. The next day would be the start of next month, target 1. So C_t = 1, and T[t] = 1, so they match again! So interestingly, if a month has exactly d days, the auto increment after the last day yields 1, which matches the next month's first day. So no manual adjustment needed at that boundary. In fact, manual adjustments only occur when the auto increment from the previous day's target does not equal the current day's target. That is, inc_t > 0 iff C_t != T[t] i.e., iff (T[t-1] + 1) mod d != T[t] (for t>1). For t=1, C1=1, T1=1 always? Actually T1 is always 1 because first day of first month is day 1. So inc1=0. So overall, we can compute total increments as sum over all transitions between consecutive days of the "mismatch" amount, i.e., the forward distance from (T[t-1] + 1) mod d to T[t].
But careful: inc_t = (T[t] - C_t + d) % d, with C_t = (T[t-1] + 1) mod d for t>1. So inc_t = (T[t] - ((T[t-1]+1) mod d) + d) % d.
Thus total manual increments = Σ_{t=2}^{N} f(T[t-1], T[t]), where f(x, y) = (y - ((x+1) mod d) + d) % d. Also include t=1? Since C1=1 and T1=1, inc1=0 anyway, so can ignore.
So the problem reduces to: given the sequence T[1..N] that consists of blocks: for each month i, it's 1,2,...,a_i. Compute sum over t from 2 to N of g(x = T[t-1], y = T[t]), where g(x,y) = (y - ((x+1) mod d) + d) % d.
We need to compute this efficiently without iterating over each day individually, because N could be up to sum a_i, which may be large (n up to 2000, each a_i up to 1e6 => total up to 2e9). However, note that within a month, the sequence is consecutive integers from 1 to a_i. So the transitions between consecutive days within the same month can be handled in bulk.
Let's analyze the transition from one day to the next, within a month.
Within a month i, we have days: 1,2,3,...,a_i. For transitions from day k to k+1 (where 1 ≤ k < a_i), we have x = k, y = k+1. Compute g(k, k+1) = ((k+1) - ((k+1) mod d) + d) % d.
But careful: (x+1) mod d = (k+1) mod d, because x+1 = k+1. Since k+1 ≤ a_i ≤ d, and also k+1 ≤ d? Actually k ≤ a_i -1, so k+1 ≤ a_i ≤ d, so k+1 is ≤ d. But it could be equal to d if a_i = d and k = d-1. In that case (k+1) = d, and (k+1) mod d = 0? But our representation is numbers from 1 to d. The operation ((x+1) mod d) we defined as: if x+1 == d+1 then 1, else x+1. So we need to be careful with modulo representation. The usual mod d with values in 1..d: define function next(x) = x+1 if x<d else 1. That's equivalent to ((x-1+1) mod d)+1? Let's set values 0..d-1 maybe easier. Let's convert to 0-indexed to simplify modulo arithmetic.
Define values in [0, d-1] representing day numbers: actual day number (1..d) corresponds to value (day -1) mod d. So let:
- Let cur' = (cur - 1) mod d (in 0..d-1)
- Let target' = (target - 1) mod d.
Then the clock increments: next(cur') = (cur' + 1) mod d. Manual adjustment from cur' to target' requires a forward distance: (target' - cur' + d) % d (since we increment by 1 each time, which corresponds to adding 1 mod d). And after manual adjustment, cur' = target', then auto increment yields next cur' = (target' + 1) mod d.
Thus we can work mod d in 0..d-1.
Let’s define:
Let a_i' = a_i (but in 0-indexed, the day numbers: day 1 -> 0, day 2 -> 1, ... day a_i -> a_i-1). But we can keep track.
Sequence T'[t] = (actual day number - 1) mod d, i.e., for day number D in 1..a_i, T' = D-1.
Within a month, T' runs: 0,1,2,...,a_i-1.
C'_t is the clock display at start of day t in 0-indexed (value 0..d-1). Initially C'_1 = 0 (since day 1 shows 1 => 0). Then for each day:
inc_t = (T'[t] - C'_t + d) % d.
After manual: C'_t becomes T'[t].
Then auto increment: C'_{t+1} = (T'[t] + 1) mod d.
So the transition for t>1: C'_t = (T'[t-1] + 1) mod d.
Thus inc_t = (T'[t] - ((T'[t-1] + 1) mod d) + d) % d.
Now, within a month, for consecutive days: T'[t-1] = k-1 (where k from 1 to a_i-1) and T'[t] = k.
Then T'[t-1] + 1 = k, and (T'[t-1] + 1) mod d = k mod d. Since k ≤ a_i - 1? Actually k runs from 1 to a_i-1? Let's check: For transition from day k to k+1 in original numbers, in 0-indexed: from (k-1) to k? Actually original day numbers: x = k, y = k+1. In 0-indexed: x' = k-1, y' = k. Then x'+1 = (k-1)+1 = k. So the next clock start C'_t = (x' + 1) mod d = k mod d. But note that y' = k. So inc = (k - (k mod d) + d) % d. But since k is less than d? Actually k ≤ a_i - 1 ≤ d-1 because a_i ≤ d. So k is in 0..d-1. Thus k mod d = k. Therefore inc = (k - k) % d = 0. So within a month, as long as we are not dealing with a wrap from d to 1 (i.e., from day d to day 1), inc is zero. But wait, what about the case when a_i = d? Then within the month, the last transition from day d-1 to day d? Let's examine: original days: x = d-1, y = d. In 0-indexed: x' = d-2, y' = d-1. Then x'+1 = d-1, which is y', so inc = 0. So within a month, all consecutive day transitions yield inc = 0, because the auto increment gives exactly the next day's number, since the day numbers increase by 1 and are within 1..d (or 0..d-1). So manual adjustments are never needed within a month. The only potential mismatches occur at month boundaries, i.e., between the last day of month i and the first day of month i+1. But also possibly if a month ends exactly at d and the next month starts at 1, then the auto increment after d gives 1, which matches, so no adjustment needed. So manual adjustments occur only at boundaries where the last day of a month is not d, so the auto increment gives last_day+1, while the next month's first day is 1, causing mismatch. Additionally, what about the start of the year? That is fine as we start with 1 and it matches.
Thus, we can simplify: The total number of manual increments equals the sum over month transitions (i from 1 to n-1) of the amount needed to adjust from the clock's value after auto increment from the last day of month i to the first day (1) of month i+1, plus possibly adjustments needed at the start of the year? But start is fine. Also, what about the very first day? Not needed.
But careful: Are there any other mismatches? Let's double-check with sample 2: months: 3,4,3. Within month1: no adjustments. After month1, last day is 3. Auto increment from 3 gives 4. Next month first day is 1. So mismatch: need to go from 4 to 1, which is forward distance: from 4 to 1: going 4->5? Actually d=5, 4->5->1? But we need forward increments only, so from 4, increments: 4->5 (1), 5->1 (1) => total 2. That's the inc on day 4 (first day month2). That matches. After month2, last day is 4. Auto increment from 4 gives 5. Next month first day is 1. Mismatch: from 5 to 1: forward distance: 5->1? Since wrap, from 5, increment: goes to 1 (since 5+1=6 wraps to 1). So that is 1 step. So total = 2+1 = 3. So indeed only month boundaries contributed.
But what if a month ends at d? Then auto increment from d gives 1, matching next month's first day (1). So no adjustment needed at that boundary. So the only adjustments needed are at boundaries where the last day of month i (a_i) is not equal to d. However, is that all? Let's test a scenario where month i has a_i days, and month i+1 also has a_{i+1} days. At the boundary, we have:
- Last day of month i: target L = a_i (original number). After adjustments on that day, clock shows L. Then auto increment: new clock start for next day = next(L) = L+1 if L < d else 1.
- Next day's target is F = 1 (since month i+1 starts at day 1). So mismatch occurs if next(L) != F, i.e., if L < d then next(L) = L+1, which is not 1 unless L+1 = 1 mod? L+1 is between 2 and d (since L ≤ d-1). So it never equals 1. So indeed, if L < d, next(L) != 1, so mismatch. If L = d, next(L) = 1, matches. So it's exactly that.
Thus total manual increments = sum over i from 1 to n-1 of inc_i, where inc_i = distance from next(L_i) to 1, i.e., the number of manual increments needed on the first day of month i+1. But note that inc_i is the forward steps from clock start (which is next(L_i)) to target 1. That distance is: if next(L_i) = L_i+1 (since L_i < d), then we need to go from L_i+1 to 1 by incrementing: that is (1 - (L_i+1) + d) % d = (d - L_i) % d? Let's compute: (1 - (L_i+1) + d) % d = (d - L_i) % d. Since L_i is between 1 and d-1, d - L_i is between 1 and d-1. That seems plausible. For L_i = d-1, d - (d-1) = 1, correct (sample: L_i=4, d=5 => d-4=1). For L_i=2, d=4 => d-2=2 (sample 1: d=4, a1=2, L1=2 => d-2=2, matches inc at boundary=2). So inc_i = d - a_i, provided a_i < d. If a_i = d, then inc_i = 0 because no mismatch.
But is there any scenario where there might be manual adjustments within a month due to wrap? Consider a month where a_i is less than d, but the day numbers within month are always less than d, and auto increments always yield the next day number as long as the next day number is ≤ d. Since the day numbers are increasing by 1, and they stay ≤ a_i ≤ d, and if a_i = d, the last day is d, but then next day is 1 which is start of next month. So within month, no wrap occurs because we never go from d to 1 within a month unless the month includes d and then the next day in the same month would be d+1 which doesn't exist. So wrap only occurs at month boundaries, and only if the last day is d. So indeed, the only adjustments occur at boundaries where a_i < d, and the amount is d - a_i.
But wait, what about the possibility that on the first day of a month, the clock might not be mismatched only due to the boundary? Could there be cases where the clock's display is already correct because it had been manually adjusted previously? But the process we described is deterministic: after a month boundary, if a_i < d, the clock start for the next month is a_i+1. This is independent of any manual adjustments because after the last day we set it to a_i, and auto increments to a_i+1. There is no other influence. So mismatch always occurs and the amount is exactly d - a_i (since we need to go from a_i+1 to 1). However, note: if the next month's first day target is not 1? No, it's always 1. So yes.
But wait: Could there be a scenario where after the last day of a month, the clock might not be exactly at a_i because Vasya might have done manual adjustments on that last day? But on the last day, Vasya will adjust if needed; but if the clock at start of last day might not have been a_i? Let's check: At the start of the last day of month i, the clock display could be something. But after manual adjustments, it becomes exactly the target a_i. So by the end of the day (after manual), it shows a_i. So auto increment from a_i. So indeed, regardless of previous state, after the day ends, the clock is at a_i, then increments to a_i+1 (or 1). So the state at start of next month is determined solely by a_i. So the mismatch amount at the start of next month is deterministic: if a_i < d then it's d - a_i; if a_i = d then it's 0.
Thus total manual increments = sum_{i=1}^{n-1} (if a_i < d then d - a_i else 0). That is sum_{i=1}^{n-1} (d - a_i) for those a_i < d.
But wait, is that all? Let's test with sample 3: d=31, n=12, a = standard months. Compute sum for i=1..11 of (d - a_i) where a_i < d? Let's compute: a = [31,28,31,30,31,30,31,31,30,31,30,31] (last is a12). For i=1 to 11: i1 a1=31 -> equals d -> 0. i2 a2=28 <31 -> 31-28=3. i3 a3=31 ->0. i4 a4=30 ->1. i5 a5=31 ->0. i6 a6=30 ->1. i7 a7=31 ->0. i8 a8=31 ->0. i9 a9=30 ->1. i10 a10=31 ->0. i11 a11=30 ->1. Sum = 3+1+1+1+1 = 7? Let's sum: 3+1=4, +1=5, +1=6, +1=7. Yes matches sample output 7.
Great! So solution is trivial: just sum over first n-1 months: max(0, d - a_i) but a_i <= d, so it's d - a_i if a_i < d else 0. Wait, what about the case where a_i = d? then d - a_i = 0. So sum_{i=1}^{n-1} (d - a_i). That seems to be correct from examples.
But is there any other situation that could cause manual adjustments within a month? Consider the case where d is smaller than a_i? But it's guaranteed a_i ≤ d. So no.
But wait: The clock's display can only show numbers up to d. At the start of a month, the clock might show a number greater than the month's length? For the first day of month, target is 1. If a_{i-1} < d, then clock shows a_{i-1}+1. That could be > a_i? Not relevant because we adjust to 1, not to a_i. So only mismatch at first day.
What about the scenario where a_i is small, and the month ends before d? That's covered.
But what about the last month? Do we need to consider adjustments after the last day? No, because we only count manual increments up to and including the last day. On the last day of year, we may have manual adjustments if the clock at start of last day is mismatched. Could that happen? The last day is part of month n. The start of the last day is determined by the previous day's auto increment. The previous day is the second last day of month n, which is within the same month. Since within a month there is no mismatch, the start of the last day should be correct: if the last day is day a_n, and the previous day is a_n - 1, then start of day a_n should be (a_n - 1)+1 = a_n, because after the previous day, we set to a_n-1, then auto increment to a_n. So it matches. So no adjustment on last day (unless there is a mismatch due to wrap? Let's examine if a_n = d? Then the previous day is d-1, auto increment to d, matches last day d. So fine. If a_n = 1? Then the month has only one day. For month n with a_n = 1, the previous day is from month n-1's last day. So start of month n day 1 is determined by a_{n-1}. If a_{n-1} < d, then start = a_{n-1}+1, target =1, so there will be a mismatch on the first day of month n. That's accounted for in the boundary sum (i = n-1). And then after that day, there is no further day in year, so we don't need to consider after last day. And on that day, we counted the manual increments as part of boundary sum? Wait, the boundary sum includes i from 1 to n-1, each boundary between month i and i+1. So for i=n-1, it covers transition from month n-1 to month n, which includes the first day of month n. That's exactly the day we might need to adjust. So it's included. Then after that day (if it's the last day of year because a_n=1), there is no next day. So no further adjustments. So sum over i=1..n-1 of (d - a_i) (if a_i < d) counts all manual increments needed on first days of months 2..n. But is there any manual increment on the first day of month 1? No, because clock starts at 1 and matches. So all good.
Thus answer = Σ_{i=1}^{n-1} (d - a_i) where a_i < d. Equivalent to Σ_{i=1}^{n-1} (d - a_i) because if a_i = d, then term = 0 anyway. So answer = Σ_{i=1}^{n-1} (d - a_i). But careful: if a_i can be equal to d, d - a_i = 0, so sum still works. So answer = (n-1)*d - Σ_{i=1}^{n-1} a_i. That is simple.
But wait, check sample 1: d=4, n=2, a=[2,2]. Then answer = (1)*4 - 2 = 2. Yes. Sample2: d=5, n=3, a=[3,4,3]; sum_{i=1}^{2} a_i = 3+4=7; (2)5 - 7 = 10-7=3. Yes. Sample3: d=31, n=12; sum_{i=1}^{11} a_i = total days of year minus a_12 = 365? Actually standard year: sum = 365? 31+28+31+30+31+30+31+31+30+31+30 = 31+28=59, +31=90, +30=120, +31=151, +30=181, +31=212, +31=243, +30=273, +31=304, +30=334. So sum first 11 months = 334. Then answer = 1131 - 334 = 341 - 334 = 7. Yes.
Thus solution is trivial.
But wait, is there any hidden nuance? Let's double-check problem statement: "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." So yes.
But what about the case where a_i may be equal to d? We said inc at boundary = 0. But is there any scenario where within a month with a_i = d, the clock might need adjustment on the first day of that month? If a_i = d, it's not the first month, then the boundary from previous month to this month: if previous month's a_{i-1} < d, then the clock start for this month is a_{i-1}+1. But target is 1 (since month i starts at day 1). So there is a mismatch! Wait, we previously assumed that if a_{i-1} < d, the mismatch occurs regardless of a_i. But we accounted that as inc_i for i-1 boundary. But now consider month i which has a_i = d. On its first day, target is 1. The clock start is from previous month: next(a_{i-1}) = a_{i-1}+1 if a_{i-1}<d, else 1 if a_{i-1}=d. So if a_{i-1}<d, then start = a_{i-1}+1 ≠ 1, so there is a mismatch on day 1 of month i. That's accounted as inc_{i-1} = d - a_{i-1} (if a_{i-1}<d). That's fine. So our sum includes that, because we sum over i=1 to n-1, where each term corresponds to the mismatch at the start of month i+1. So if month i+1 has a_i+1 = d, it's still included because we use a_i (the preceding month) to compute the term. So if a_i = d, term = 0, meaning no mismatch at start of month i+1? But that would imply that if a_i = d, the next month's first day does not need adjustment. Let's test: Suppose d=5, months: a1=5, a2=3. After month1: last day 5, auto increment from 5 gives 1. So start of month2 day1: clock shows 1, target =1, so no manual adjustment. So indeed, if a_i = d, the boundary has no adjustment regardless of a_{i+1}. So term for i=1 would be d - 5 = 0, correct. So sum formula works.
Now what about the case where a_i = d and a_{i+1} also = d? Then after month i, auto increment gives 1, matches first day of month i+1 =1, no adjustment. So term =0.
Thus answer is simply sum over first n-1 months of (d - a_i). But is it always exactly that? Let's test a more complex scenario to be sure: d=6, months: a=[3, 2, 6, 1]. Let's manually simulate.
- Month1: days 1,2,3. Start cur=1. Day1: match, inc0; auto to 2. Day2: match, inc0; auto to 3. Day3: match, inc0; auto to 4 (since 3<6 -> 4).
- Month2 day1: cur=4, target=1 -> inc = (1-4+6)%6=3? (6-3=3) Actually (1-4+6)=3, inc=3. So manual 3 steps (4->5->6->1). After adjust to 1, auto to 2? Wait after day, auto increments: from 1 to 2.
- Month2 day2: cur=2, target=2 -> inc0; auto to 3 (since 2<6 ->3). End month2 with a2=2.
- Month3: days 1..6. Start day1: cur=3 (from previous auto), target=1 -> inc = (1-3+6)%6=4? (6-2=4?) Actually (1-3+6)=4, inc=4. Manual steps: 3->4,4->5,5->6,6->1: 4 steps. After adjust to 1, auto to 2.
- Then month3 days 2: cur=2 target=2 inc0 auto3
- day3: cur=3 target=3 inc0 auto4
- day4: cur=4 target=4 inc0 auto5
- day5: cur=5 target=5 inc0 auto6
- day6: cur=6 target=6 inc0 auto? After day6, auto increments: since 6=d, auto to 1.
- Month4 day1: cur=1, target=1 -> inc0. End of year.
Total manual increments = at start of month2:3, at start of month3:4, total=7.
Now compute formula: sum_{i=1}^{3} (d - a_i) for i=1..3 (since n=4, sum i=1..3). d=6. i1: a1=3 -> 6-3=3 i2: a2=2 -> 6-2=4 i3: a3=6 -> 6-6=0 Sum=7. Correct.
So indeed works.
But is there any possibility of manual adjustments on the last day of year if the last month's a_n < d? Let's test: d=5, months: a=[2,2]. This we did: inc at start of month2 = d - a1 = 3? Wait d=5, a1=2 -> 5-2=3. But earlier we computed manually for d=4, a1=2 gave 2. So for d=5, a1=2, a2=2. Simulate: month1 days 1,2. Start cur=1. Day1 inc0 auto2. Day2 inc0 auto3? Actually after day2 auto: from 2 -> 3 (since <5). Then month2 day1: cur=3, target=1 -> inc = (1-3+5)%5 = 3. Manual steps: 3->4,4->5,5->1 = 3. Then day2: after day1 manual, cur becomes 1 after adjustments? Actually after adjustments, we set to 1, then auto? Wait sequence: At start of day1 month2, cur=3. We do manual increments: 3->4 (1), 4->5 (2), 5->1 (3). After these, clock shows 1. Then at end of the day, auto increments to 2. So start of day2 month2, cur=2, target=2, inc0. So total manual=3. That matches formula (5-2=3). So last day no adjustment.
What about scenario where a_n=1 and a_{n-1}<d? Then start of month n day1 needs adjustment as per boundary, which we count. And then month n ends after that one day, and we don't need further adjustments. So all good.
Thus answer is simply sum_{i=1}^{n-1} (d - a_i). Since d and a_i up to 1e6, n up to 2000, sum fits in up to (2000-1)*1e6 = about 2e9, which fits in 64-bit. So we can compute with 64-bit integer.
But wait, there's a nuance: the problem says "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." So manual increments also wrap. That's consistent.
Now, check if there is any possibility of manual adjustments on the first day of the year if the clock didn't start at 1? It starts at 1, so no.
Now, what about the case where d=1? Then a_i ≤ d =1, so each month has exactly 1 day. The clock can only display 1. On day1 of month1: clock shows 1, matches. After the day, auto increment: from 1, since d=1, next(1) = 1 (wrap to 1). So start of month2 day1: clock shows 1, target=1, matches. So no manual adjustments ever. According to formula: sum_{i=1}^{n-1} (d - a_i) = sum (1 - 1) = 0. Good.
Now, what about d=1, but a_i can be 1 only. So formula works.
Now, what about d=2, months: a=[1,2]. Let's simulate: month1 day1: cur=1 target=1 inc0 auto: from 1 to 2? Since d=2, 1+1=2, so cur=2. Month2 day1: cur=2 target=1 -> inc = (1-2+2)%2 = 1? (1-2+2=1) inc=1. Then after manual, cur becomes 1, auto? But after day, auto increments: from 1 to 2. End. Total inc=1. Formula: sum i=1 to 1: d - a1 = 2-1=1. Good.
Now consider d=2, a=[2,1]. Month1: days 1,2. Start cur=1, day1 inc0 auto2, day2: cur=2 target=2 inc0 auto? After day2, since d=2, auto from 2 -> 1. Month2 day1: cur=1 target=1 inc0. So total inc=0. Formula: sum i=1 to 1: d - a1 = 2-2=0. Good.
Now consider d=2, a=[2,2]. Month1: days1,2: cur1=1 day1 inc0 auto2, day2 cur=2 inc0 auto -> after day2, auto from 2->1. Month2 day1: cur=1 target=1 inc0 auto2, day2 cur=2 target=2 inc0. So total inc=0. Formula: d - a1 = 0, sum =0. Good.
Now, consider d=2, a=[1,1,1]. Month1 day1: cur1=1 inc0 auto2. Month2 day1: cur=2 target=1 inc1, after manual to 1 auto2. Month3 day1: cur=2 target=1 inc1, total inc=2. Formula: sum over i=1,2: d - a_i = (2-1)+(2-1)=1+1=2. Good.
Thus formula holds.
But wait, is there any scenario where Vasya might need to manually increment more than once on a day? That's captured by the forward distance. In our derived sum, we counted the entire forward distance for each boundary. That's correct.
Now, what about transitions within a month? We argued they are always zero because the clock auto increments to exactly the next day's number. But is that always true if a_i < d? Let's consider a month where a_i = 3, d=4. Within month: days 1,2,3. The auto increments: after day1 (target 1) -> 2; after day2 (target 2) -> 3; after day3 (target 3) -> 4. So start of next day within month: for day2 start=2 matches target 2; day3 start=3 matches target 3. So no manual. So correct.
What about if a_i = d? Then within month, say d=4, a_i=4. Days: 1,2,3,4. After day1: 2; day2 start 2 matches; after day2: 3; day3 start 3 matches; after day3: 4; day4 start 4 matches; after day4: auto from 4 -> 1. So within month, all match. Good.
What about the case where a_i = 0? Not possible because a_i ≥ 1.
Thus, it seems the answer is sum_{i=1}^{n-1} (d - a_i). However, wait a moment: Is there any scenario where Vasya might need to manually adjust on the first day of the first month? The problem says the clock initially shows 1. The actual day is day 1 of month 1. So match. So no.
But what about the scenario where the clock automatically increments at the start of the day rather than at the end? The description: "when a new day comes, it simply increases the current day number by one." It doesn't specify exactly when, but the example shows that the increment happens before Vasya's check? Or after? Let's re-read the narrative carefully:
"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."
"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."
It says "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)." So the automatic increment occurs "when a new day comes", i.e., at the transition from one day to the next. So at the start of a new day, the clock has already been incremented automatically. Then Vasya checks it. In the example: Day 1 month 1: clock shows 1. Then after day 1, it increments? Actually the example describes: "Day 1. Month 1. The clock shows 1. Vasya changes nothing." Then "Day 2. Month 1. The clock shows 2. Vasya changes nothing." That implies that after day 1, the clock automatically incremented to 2 before day 2 begins. So yes, the automatic increment happens at midnight, before Vasya checks. So our model (C_{t+1} = (T[t] + 1) mod d) is correct.
Thus answer as derived.
But wait, is there any situation where Vasya might need to adjust on a day after a month boundary even if the auto increment from previous month's last day yields a value that matches the first day of next month? That would be when a_i = d, then auto yields 1, matches, so no adjustment.
Thus answer is simply Σ_{i=1}^{n-1} (d - a_i). But wait, let's test a case where a_i is small and d is large, but the clock might have been manually adjusted previously in such a way that on a day later in the month, the clock might be off due to previous adjustments? But we argued that within a month, after any day, we set the clock to the correct day number, and auto increment gives the next day number exactly. So no drift can accumulate because each day we correct it exactly. So any mismatch only arises from the auto increment not aligning with the next target because the target resets to 1. So indeed.
But let's test a more complex scenario: what if a month has a_i = d-1, and the next month has a_{i+1}=1. Then after month i, auto increment from d-1 gives d. On the first day of month i+1, target=1, so mismatch, need to go from d to 1: that's 1 step (d -> 1). Our formula gives d - a_i = d - (d-1) = 1, correct.
What if a_i = d-1 and a_{i+1}=2? Actually still mismatch at start of month i+1 because start = d, target=1, inc = d - a_i = 1. Then after that day, clock becomes 1 after manual, then auto increments to 2, which matches day2 of month i+1 (if a_{i+1} >=2). So no further adjustments. Good.
Now, consider a scenario where there are multiple months, and after a month with a_i = d, the next month starts with no adjustment. But if the next month also has a_{i+1} < d, then after that month's last day, which is a_{i+1} < d, there will be an adjustment at the following boundary. So formula still sums over i from 1 to n-1 of d - a_i, i.e., it counts adjustments at boundaries between month i and i+1. So each boundary's adjustment depends only on a_i, not on a_{i+1}. That seems consistent.
But wait, what about the scenario where the last month's a_n is less than d? Does that produce any adjustment after the year? No, because we don't count after the last day. So it's fine.
Now, confirm with a more exotic case: d=10, months: a=[5,5,5]. Simulate quickly:
Month1: days1..5: all match. After day5 auto from 5 to 6. Month2 day1: cur=6 target=1 inc = (1-6+10)%10 =5? Actually (1-6+10)=5, inc=5. That's d - a1 = 10-5=5. Then after adjusting to 1, auto to 2. Day2: cur=2 target=2 ok, auto3 Day3: cur=3 target=3 ok auto4 Day4: cur=4 target=4 ok auto5 Day5: cur=5 target=5 ok auto6 Month3 day1: cur=6 target=1 inc=5 (d - a2 =5). Then day2..5 match. Total inc=5+5=10. Formula: sum_{i=1}^{2} (10-5)=5+5=10. Good.
Now, consider case where a_i can be 0? No.
Thus solution appears extremely simple. But we must be absolutely certain there is no hidden nuance such as: Vasya checks the clock at the beginning of each day, but what if the automatic increment occurs after he checks? That would change things. But the example clearly indicates that the automatic increment happens before he checks on the new day. Let's reexamine example statement: "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 ...". It doesn't explicitly mention the automatic increment, but the fact that on day2 it shows 2 implies that after day1, the clock moved to 2. So indeed the automatic increment occurs and then Vasya checks. So correct.
Now, could there be any scenario where the clock's manual adjustment is done after the automatic increment? But Vasya only checks at the beginning of the day, before any manual adjustments. The automatic increment already happened at midnight. So we are good.
Thus the problem reduces to a trivial sum.
But wait, the problem statement also says: "The clock's face can display any number from 1 to d. It is guaranteed that ai ≤ d for all i from 1 to n." So that's fine.
Thus the answer is sum_{i=1}^{n-1} (d - a_i). That is O(n). But is there any need to consider the last day's automatic increment causing an adjustment? No.
Edge Cases: n=1. Then there are no boundaries. So total manual increments should be 0. Our formula sum from i=1 to n-1 yields empty sum = 0. Good. Check: If only one month, start with cur=1, all days within month match automatically because the auto increment from day to day yields the correct next day, and the first day matches. So no manual increments. For example, d=5, a=[3]. Simulate: Day1: cur1=1 target1=1 inc0 auto2; Day2: cur2=2 target2=2 inc0 auto3; Day3: cur3=3 target3=3 inc0. Total 0. So correct.
But wait, what about the scenario where the month's length is less than d but the auto increment after the last day of the year might cause the clock to show something else, but we don't care because we stop at the last day. So all good.
Thus the answer is straightforward.
Now, confirm with given examples: matches.
Now, let's consider a more random test: d=100, n=4, a=[50, 100, 50, 100]. Compute manually: sum i=1..3 (d - a_i) = (100-50)=50, then (100-100)=0, then (100-50)=50 => total 100. Let's simulate conceptually: month1: 1..50: all match. After day50, auto to 51. month2 day1: cur=51 target=1 -> inc =? 1-51+100=50 -> inc=50. So after adjustment to 1, auto to 2. month2 has 100 days: all match because within month it's consecutive and final day is 100. After day100, auto from 100 to 1. month3 day1: cur=1 target=1 inc0? Actually auto from 100 gives 1, matches first day of month3 (target=1). So no adjustment at this boundary because a2=100. Then month3: days1..50: all match? After day50, auto from 50 to 51. month4 day1: cur=51 target=1 -> inc = 50. So total 100. Good.
Thus consistent.
Now, think about potential overflow: d up to 1e6, n up to 2000, sum up to 2e9, fits in 32-bit signed? 2e9 is borderline for 32-bit int (max 2,147,483,647). It could be exactly 2e9 = 2,000,000,000 which is less than 2,147,483,647, so safe for int. But to be safe, we can use long long.
Now, we should confirm that no manual increments are needed within month when a_i is exactly d but there is a wrap at the last day? Actually within month, at the last day, after the day we set clock to d, then auto increments to 1, but that's after the day; the next day is next month's first day. So within month, no issues.
Thus solution is correct.
But wait, I recall some Codeforces problem "Vasya and the Clock" maybe similar? I think it's from Codeforces Round? Actually I remember a problem "Vasya and the Clock" that had a similar trick. The answer was sum (d - a_i) for i < n. Indeed.
Thus we can implement.
But let's double-check the initial condition: "on the first day of the first month the clock display showed day 1." So cur1 = 1. That's consistent.
One more check: if d is very small and a_i are all d, then answer 0. Good.
Now, why did they include the constraint n ≤ 2000? Possibly to allow O(n) solution. But our O(n) solution is trivial. They might have expected the summation method.
Thus final solution: read d, n, list a. Compute sum = 0; for i in range(n-1): sum += d - a[i]; print sum.
But wait, careful: The input format: first line d, second n, third line a_i. There's a sample with d=31, n=12, a list of 12 numbers. So we need to read exactly n numbers.
We need to ensure that we do not accidentally include the last month's a_n in the sum. So only first n-1.
Edge case: n=0? n≥1.
Now, let's consider potential pitfalls: Could there be a scenario where the clock's auto increment and manual adjustment might interfere if the manual adjustment on a day is done after the auto increment? No, because Vasya only adjusts at beginning of day.
Thus answer stands.
Given the simplicity, I'm confident.
But let's thoroughly prove it.
We have:
Let C_t be clock value at start of day t. C_1 = 1.
For each day t, with target T_t (actual day of month), manual increments M_t = (T_t - C_t) mod d (in 1..d representation). Actually careful: Using 1..d, we need to compute the number of increments: To go from current display x to target y, Vasya presses until the display becomes y. Since each press increases by 1 (with wrap after d), the number of presses is: if y ≥ x then y-x; else (d - x) + y. That is (y - x + d) % d.
After adjustments, display becomes y. Then at midnight, automatic increment: display becomes next(y) = y+1 if y < d else 1.
So C_{t+1} = next(y) = next(T_t).
Thus for t>1, C_t = next(T_{t-1}).
Now, T_t is defined as:
For month i, for day number d_i = 1,2,...,a_i.
So T_t sequence is: 1,2,...,a_1, 1,2,...,a_2, ..., 1,...,a_n.
Now compute M_t for t>1: M_t = (T_t - next(T_{t-1}) + d) % d.
Now, note that for t such that both T_t and T_{t-1} are within the same month and T_t = T_{t-1}+1 (i.e., not the last day of month), we have T_t = T_{t-1}+1. Also, since T_{t-1} ≤ a_i ≤ d and T_{t-1} < d (because if T_{t-1} = d, then it would be last day and the next day would be start of next month, so T_t would not be T_{t-1}+1, but rather 1). So T_{t-1} < d, thus next(T_{t-1}) = T_{t-1}+1 = T_t. Therefore M_t = 0.
For t where T_{t-1} is the last day of month i (i.e., T_{t-1}=a_i) and T_t is the first day of month i+1 (i.e., T_t = 1), we have:
- If a_i = d, then next(T_{t-1}) = 1, so M_t = (1 - 1 + d) % d = 0.
- If a_i < d, then next(T_{t-1}) = a_i + 1, so M_t = (1 - (a_i+1) + d) % d = (d - a_i) % d. Since a_i < d, d - a_i ∈ [1, d-1], so M_t = d - a_i.
Thus, the only nonzero M_t occur at boundaries between months where the preceding month's length a_i < d. And each such boundary contributes exactly d - a_i manual increments. There are n-1 boundaries. Therefore total manual increments = Σ_{i=1}^{n-1} (d - a_i) where a_i < d, which simplifies to Σ_{i=1}^{n-1} (d - a_i) because if a_i = d, term is 0.
Thus answer = (n-1)*d - Σ_{i=1}^{n-1} a_i.
This is O(n). Constraints allow.
Now, implement.
But wait, one more nuance: The problem says: "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." That means he will keep pressing until it matches. That matches our forward distance.
Now, what about the scenario where on a day, the clock shows a number that is already greater than the target? He still increments until it wraps around to the target. That's accounted by mod.
Now, double-check: Is there any possibility that on a day, the clock might be behind (i.e., less than target) but also need to wrap? Actually if cur < target, then forward distance is target - cur, no wrap. If cur > target, wrap.
Now, in our boundary case where cur = a_i+1 and target = 1, since a_i+1 > 1 (unless a_i = d, then a_i+1 wraps to 1, but we handle that as cur=1). So for a_i < d, cur > target, wrap needed. The distance is (d - cur) + target = (d - (a_i+1)) + 1 = d - a_i. So correct.
Thus answer stands.
Now, check sample 1: d=4, n=2, a=[2,2]. sum_{i=1}^{1} (4-2)=2 -> matches.
Now, note: The problem says "from the first day of the first month to the last day of the n-th month inclusive". So our sum counts adjustments on the first day of month i+1 for i=1..n-1, which are included, and does not count anything after the last day. So correct.
Now, we must ensure we interpret input correctly: first line d, second n, third line n integers. So implement reading.
Now, edge case: n can be 2000, d up to 1e6, sum might be up to (1999)*1e6 ~ 1.999e9, which fits in int? Actually 2e9 is borderline but within 32-bit signed int (max 2,147,483,647). However, if d=1e6 and n-1=1999, product = 1,999,000,000, which is less than 2,147,483,647, so int works. But to be safe, use long long.
Now, answer can be zero.
Implementation in C++: read, compute sum_a_first_n_minus_1 = accumulate(a, a+n-1, 0LL). Then ans = (n-1)1LLd - sum.
But careful: if n=1, (n-1)*d = 0, sum is 0, ans=0. Works.
Thus final solution.
But wait: is there any scenario where the clock's automatic increment might be suppressed because Vasya manually increments? No, the automatic increment is a separate mechanism that always occurs when a new day comes, regardless of manual adjustments. So it's fine.
Thus answer is trivial.
However, before finalizing, I want to think if there is any hidden trick where manual increments might be needed within a month if a_i > d? Not allowed. Or if the clock's display range is 1..d, but the actual day numbers are ≤ d, so no.
Also, consider scenario where a_i = 0? Not possible.
Thus I'll adopt the simple solution.
But let's see if the problem could have been misinterpreted: Could it be that the clock's automatic increment happens after Vasya checks and after he possibly manually increments? The phrasing "when a new day comes, it simply increases the current day number by one." This might imply that the new day starts, and then the clock increments? But then Vasya checks the day number. Typically, one would think that at the start of the day, the clock shows the number from the previous day (maybe after auto increment at midnight). Actually the phrase "when a new day comes" is ambiguous: it could mean at the moment the day begins, the clock increments. That is what we assumed. Alternatively, could it mean that sometime during the day (maybe at a specific time) the clock increments? But the example clarifies: on day2, the clock shows 2, which is the incremented value from day1. So it's consistent that the increment occurs before Vasya checks.
Thus okay.
Now, check the note: In the first sample, they describe: 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 ... After that the clock shows 4. Vasya increases ... After that the clock shows 1. Day 2. Month 2. The clock shows 2. So indeed, after manual adjustments on day1 month2, they didn't mention an automatic increment before day2 month2? They say after manual adjustments, the clock shows 1, and then "Day 2. Month 2. The clock shows 2." How did it become 2? It must have automatically incremented at the start of day2. So they omitted that step in description, but it's implied. So our model is consistent.
Thus final answer.
Now, is there any scenario where on a day, after manual adjustments, the clock shows the correct number, but then the automatic increment (at midnight) might cause the next day's start to be off even if the next day's target is the next consecutive number? That's what we accounted: within month, it matches. At boundaries, mismatch.
Thus done.
Now, we should implement.
But wait, the problem title? It might be from Codeforces Round #... Anyway.
One more check: Could there be a scenario where the clock's display is wrong at the start of a day within a month because of previous manual adjustments that overshot? But manual adjustments always set to the exact target. So after the day, it's exactly correct. Then auto increment yields exactly the next day number, provided the next day number is within the month. So no.
Thus final answer.
Implementation details: read integers, compute sum of first n-1 elements, compute answer = (n-1)*d - sum. Output.
Edge Cases:
-
n=1: answer 0.
-
d = 1, a_i = 1 for all: answer 0.
-
large values: fine.
Thus solution is O(n).
Now, just to be safe, test random small cases with brute force simulation to confirm formula. I'll mentally test a few.
Case: d=3, n=3, a=[1,2,3].
Simulate:
Day1 month1: cur1=1 target1=1 inc0 auto->2. Month1 over? Actually month1 only one day: after day1 auto->2. Month2 day1: cur=2 target=1 inc = (1-2+3)%3=2? (1-2+3=2) inc=2. After manual: set to 1, auto->2. Month2 day2: cur=2 target=2 inc0 auto->3? Actually after day2, auto from 2->3. Month3 day1: cur=3 target=1 inc = (1-3+3)%3=1 inc=1. After manual: set to 1, auto->2. Month3 day2: cur=2 target=2 inc0 auto->3. Month3 day3: cur=3 target=3 inc0. Total inc = 2+1 = 3.
Formula: sum i=1..2 (d - a_i) = (3-1)+(3-2)=2+1=3. Good.
Case: d=3, a=[2,2,2].
Simulate:
Month1: days1,2. Start cur1=1 day1 inc0 auto2, day2 cur=2 target2 inc0 auto3. Month2 day1: cur=3 target=1 inc = (1-3+3)%3=1 inc=1; after manual to1 auto2. Day2: cur=2 target2 inc0 auto3. Month3 day1: cur=3 target1 inc1; after manual to1 auto2; day2 cur=2 target2 inc0. Total inc=1+1=2.
Formula: sum i=1..2 (3-2)=1+1=2. Good.
Case: d=3, a=[3,1].
Sim: Month1 days1,2,3. cur1=1 day1 inc0 auto2 day2 cur=2 target2 inc0 auto3 day3 cur=3 target3 inc0 auto1 (since d=3, 3->1) Month2 day1: cur=1 target1 inc0. Total inc=0. Formula: sum i=1..1 (3-3)=0. Good.
Case: d=3, a=[2,3].
Sim: month1: day1 inc0 auto2, day2 inc0 auto3. Month2 day1: cur=3 target1 inc = (1-3+3)%3=1 inc=1; auto2; day2 cur=2 target2 inc0 auto3; day3 cur=3 target3 inc0. Total inc=1. Formula: sum i=1..1 (3-2)=1. Good.
Thus matches.
So answer is clear.
Now, I'll produce final solution.
But wait, what if the problem had a twist: The clock's manual operation also increments by one, but Vasya might press multiple times, but the clock's auto increment might be considered as also happening? No.
Thus final answer.
Now, I'll write solution.
Implementation in Python:
def solve(): import sys data = sys.stdin.read().strip().split() if not data: return d = int(data[0]) n = int(data[1]) a = list(map(int, data[2:2+n])) total = 0 for i in range(n-1): total += d - a[i] print(total)
But ensure that a length is n. Could be extra spaces, but reading all is fine.
Now, can we compute more elegantly: total = (n-1)*d - sum(a[:n-1]).
Now, what about large input? Python can handle.
Now, final answer.
But before finishing, let's check the problem statement again: "Vasya lives in a strange world. The year has n months and the i-th month has ai 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 ai ≤ 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."
All consistent.
Now, check constraints: d up to 10^6, n up to 2000. So O(n) works.
Thus final solution is trivial.
Now, I'll produce final answer. ```python
import sys
def main(): data = sys.stdin.read().strip().split() if not data: return d = int(data[0]) n = int(data[1]) a = list(map(int, data[2:2 + n]))
# sum of d - a[i] for i = 0 .. n-2 total = 0 for i in range(n - 1): total += d - a[i] print(total)if name == "main": main()