You are given a sequence of integers a₁, a₂, ..., a_n. Let $\text{[math]}$ , and $\text{[math]}$ for 1 ≤ i < n. Here, $\text{[math]}$ denotes the modulus operation. Find the maximum value of f(x, 1) over all nonnegative integers x.

Input

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

The second lines contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10¹³) — the elements of the sequence.

Output

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

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.

Mod Mod Mod

Examples