Mod Mod Mod
Contest: Codeforces Round 445 (Div. 1, based on Technocup 2018 Elimination Round 3)
Difficulty rating: 3000
Tags: binary search, dp, math

You are given a sequence of integers a1, a2, ..., an. Let $$f(x,n) = x \bmod a_n$$, and $$f(x,i) = (x \bmod a_i) + f(x \bmod a_i, i+1)$$ for 1 ≤ i < n. Here, $$\bmod$$ denotes the modulus operation. Find the maximum value of f(x, 1) over all nonnegative integers x.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 200000) — the length of the sequence.

The second lines contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1013) — the elements of the sequence.

Output format:
Output a single integer — the maximum value of f(x, 1) over all nonnegative integers x.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example you can choose, for example, x = 19.

In the second example you can choose, for example, x = 3 or x = 2.

Example input:
2
10 5

Example output:
13

Example input:
5
5 4 3 2 1

Example output:
6

Editorial:
Hint 1: let $$x_i = x \bmod a_1 \bmod a_2 \bmod \ldots \bmod a_i$$. Can you define some interesting segments of value xi?
Hint 2: think of some dp.
Hint 3: once you get the dp in O(n2), to speed it up, note the following fact: if $$c = a \bmod b$$, then either c = a or $$c < \frac{a}{2}$$.
Explanation of hint 1: let's call ansi = f(x, 1) - f(xi, i + 1), in other words, it's the part of answer we gain from summands from 1 to i. For i = 1 the following is true: x1 can be any number from 0 to a1 - 1, and ansi = xi.
Suppose for some i we have the following option: xi can be any number from 0 to r, and in this case ansi = xi * i + k. We can describe this situation by triple (i, r, k). We will show that this triple will produce at most two such triples for i + 1. Indeed, we can have many triples (i + 1, ai + 1 - 1, kj) with different kj and one triple $$(i+1,r\mod a_{i+1},k+i\cdot(r-r\mod a_{i+1}))$$. However, we can note that among triplets of the first type we can leave only one with maximum kj, because we're interested in maximum answer. This kj will equal $$( k + i \cdot ( r - r \bmod a_{i+1} - a_{i+1} ) )$$. Thus, we have two transitions from each triple, that leads us to O(2n) bruteforce solution.
Explanation of hint 2: when we have a bruteforce, we (almost) always can think of a dp. Indeed, we have triples, among those with equal i and r let's keep only one with the largest k. There are at most i such triples on step i: on each step half of the generated triples have r = ai + 1 - 1, so we can merge them. This leads us to dp in O(n2).
Explanation of hint 3: Okay, what does the third hint say? It basically says that a number can only be taken by modulo $$O(\log(C))$$ times until it becomes zero, where C is the bound of its initial value. What do we get from this? We can note that if r < ai + 1, we can just leave a triple (i, r, k) untouched except changing i to i + 1. Let's then keep pairs (r, k), assuming triples (i, r, k), where i changes in a cycle. On each step we should change all pairs such that r ≥ ai + 1, possibly adding one more pair with r = ai + 1 - 1. But when we change a pair, r is get by modulo, so this won't happen with a pair more than O(log(C)) times! Overall, the total number of times we touch a pair is bounded by $${\mathcal{O}}(n\log(C))$$. Adding $$O(\log(n))$$ for map in which we keeps the pairs, we obtain the final complexity $$O(n \log(C) \log(n))$$. Also, map can be replaced with binary search, but the complexity remains the same.