Hide

Problem FFlip Flow

Hourglass by nile on Pixabay

For over 600 years, the hourglass has been a well-known timekeeping instrument. An hourglass consists of two glass flasks arranged one above the other which are connected by a narrow channel. Inside the hourglass there is sand which slowly flows from the upper to the lower flask. Hourglasses are typically symmetrical so that the sand always takes the same amount of time to run through, regardless of orientation. For the purposes of this problem, we also assume that the flow rate of the sand is a known constant and does not depend on the amount or distribution of sand in the upper half.

Your friend Helen was bored and has been playing around with her hourglass. At time $0$, all the sand was in the lower half. Helen flipped the hourglass over several times and recorded all the moments at which she did so. How many seconds does she need to wait from the current time until all the sand is back in the lower half?

Input

The input consists of:

• One line with three integers $t$, $s$ and $n$, where

• $t$ ($1 \le t \le 10^6$) is the current time;

• $s$ ($1 \le s \le 10^6$) is the amount of sand in the hourglass, in grams;

• $n$ ($1 \le n \le 1\, 000$) is the number of times the hourglass was flipped.

• One line with $n$ integers $a_1,\dots ,a_ n$ ($0 < a_1 < \dots < a_ n < t$), the times at which the hourglass was flipped.

All times are given in seconds. You may assume that the sand flows from the top to the bottom at a constant rate of $1$ gram per second.

Output

Output the time in seconds needed for the hourglass to run out starting from time $t$.

Sample Input 1 Sample Output 1
10 7 2
4 9

4

Sample Input 2 Sample Output 2
2000 333 3
1000 1250 1500

0

Sample Input 3 Sample Output 3
100 10 5
15 20 93 96 97

5

CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show