Problem D
Geyser Field

On Earth, a geyser is a geological feature that briefly and energetically throws out steam and hot water on a somewhat periodic basis. The Old Faithful geyser is particularly famous.
Our national space agency has a probe orbiting one of
Neptune’s moons, and it has detected a lot of geyser activity.
On this moon, isolated geysers all are very regular. If a
geyser erupts at time
There is one area that was initially mysterious, because it
seemed to have a geyser that erupted irregularly. However, the
geologists have decided that we actually have a small number
(at most
They’ve provided you with a recent history of geyser activity in this geyser field. They want to focus on the first geyser in this history, which they call Young Faithful, and they need you to predict the earliest that Young Faithful could erupt again. They hope that the history they have given you is long enough that Young Faithful will have erupted several times, but they state that that they cannot be sure.
The geologists believe that
-
only Young Faithful was erupting at the first time, but for later measurements, it is possible that several geysers might be erupting simultaneously.
-
the set of geysers has been unchanged for many years, so no new geyser is going to start erupting for the first time (or stop erupting) during the time period when measurements were taken.
-
no geyser takes longer than
time units between eruptions.
Input
The first line of the input is a positive integer
Output
The output should be an integer that indicates the earliest time that Young Faithful could erupt again, in the future. (The answer must be larger than the most recent input time.)
In the first sample data, Young Faithful could have erupted
at times
Sample Input 1 | Sample Output 1 |
---|---|
6 10 20 24 26 30 32 |
38 |
Sample Input 2 | Sample Output 2 |
---|---|
14 1000 1010 1011 1015 1020 1022 1028 1030 1035 1040 1041 1047 1060 1077 |
1080 |